> For the complete documentation index, see [llms.txt](https://mqjyl2012.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mqjyl2012.gitbook.io/algorithm/leetcode/stick-to-binary-tree.md).

# 死磕二叉树

## :pencil2: 1、`DFS`深度遍历 & 递归

###  [**Binary Tree Maximum Path Sum**](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)

给定一个**非空**二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径**至少包含一个**节点，且不一定经过根节点。

> 路径每到一个节点，有 3 种选择： 停下不走。 走到左子节点。 走到右子节点。走到子节点，又面临这 3 种选择。于是有了递归的思路。 不能走进一个分支，又掉头走另一个分支，不符合要求。
>
> 定义递归函数 
>
> 我们关心：如果路径走入一个子树，能从中捞取的最大收益，不关心具体怎么走。 这是一种属于递归的、自顶而下的思考方式。 
>
> 定义 `dfs` 函数：返回当前子树能向父节点 “提供” 的最大路径和。
>
> 向下：即，一条从父节点延伸下来的路径，能在当前子树中获得的最大收益。它分为三种情况，取其中最大的： 停在当前子树的 root，收益：root.val。 走入左子树，最大收益：`root.val + dfs(root.left)`。 走入右子树，最大收益：`root.val + dfs(root.right)`。 当遍历到 null 节点时，收益为 0，所以返回 0。
>
> 向上：如果一个子树提供的「最大路径和」为负，如下图。路径走入它，收益不增反减，我们希望这个子树完全不被考虑，所以让它返回 0，成为死支。

```cpp
int helper(TreeNode *node, int &sum){
    if(!node){
        sum = max(sum, 0);
        return 0;
    }
    int lsum = 0, rsum = 0;
    if(node->left){
        lsum = max(0, helper(node->left, sum));  // 左子树的贡献
    }
    if(node->right){
        rsum = max(0, helper(node->right, sum)); // 右子树的贡献
    }
    sum = max(sum, node->val + lsum + rsum); // 当前子树的 maxSum 挑战最大值
    return node->val + max(lsum, rsum);      // 向父节点提供的最大和，要包括自己
}
int maxPathSum(TreeNode* root){
    int maxSum = INT_MIN;
    helper(root, maxSum);
    return maxSum;
}
```

### [**Path Sum**](https://leetcode-cn.com/problems/path-sum/)

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。**（分治）**

```cpp
bool hasPathSum(TreeNode* root, int sum){
    if(!root)
        return false;
    if(root && !root->left && !root->right)
        return sum == root->val;
    return hasPathSum(root->left, sum - root->val)
        || hasPathSum(root->right, sum - root->val);
}
```

### [**Path Sum II**](https://leetcode-cn.com/problems/path-sum-ii/)

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。**（回溯）**

> 思路一：迭代，后续遍历，PATH数组和栈同步，到叶节点判断当前路径是否满足，满足就将PATH加到结果中。
>
> 思路二：递归，

## :pencil2: **2、`LCA`问题**

#### [lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。经典的`LCA（Least Common Ancestors）`问题。

> 思路一、后序遍历：**因为后序遍历的栈中始终存放着当前要访问节点的祖先节点**。所以两次后序遍历，分别遍历到两个节点位置结束，然后两个栈分别保存两个节点的祖先节点，依次弹栈，遇到第一个相同的节点即可。（最应该想到的解法）
>
> 思路二、递归：
>
> 思路三、倍增法：
>
> 思路四、欧拉序+ST表：
>
> 思路五、**`Tarjan` 算法：**

> 思路一、后序遍历：**因为后序遍历的栈中始终存放着当前要访问节点的祖先节点**。所以两次后序遍历，分别遍历到两个节点位置结束，然后两个栈分别保存两个节点的祖先节点，依次弹栈，遇到第一个相同的节点即可。（最应该想到的解法）
>
> 思路二、递归：
>
> 思路三、倍增法：
>
> 思路四、欧拉序+ST表：
>
> 思路五、**`Tarjan` 算法：**

{% tabs %}
{% tab title="后序遍历" %}

```cpp
void getAncestors(TreeNode *root, TreeNode* node, vector<TreeNode *> &astack){
    const TreeNode *cur;
    TreeNode *ptr = root;
    const TreeNode *last = NULL;
    while(ptr != NULL || !astack.empty()){
        while(ptr != NULL){
            astack.push_back(ptr);
            if(ptr == node){
                return;
            }
            ptr = ptr->left;
        }
        cur = astack.back();
        if(cur->right == NULL || cur->right == last){
            astack.pop_back();
            last = cur;
        }else{
            ptr = cur->right;
        }
    }
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    vector<TreeNode *> astack1, astack2;
    getAncestors(root, p, astack1);
    getAncestors(root, q, astack2);
    for(int i = astack1.size() - 1; i >= 0; --i){
        for(int j = astack2.size() - 1; j >= 0; --j){
            if(astack1[i] == astack2[j]){
                return astack1[i];
            }
        }
    }
    return root;
}
```

{% endtab %}

{% tab title="递归" %}

```
```

{% endtab %}
{% endtabs %}

拓展：

## :pencil2: 3、[序列化和反序列化](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/)

> 思路一：BFS 序列成对应的完全二叉树（超时，主要是字符串`split`耗时长）。
>
> 思路二：DFS 前中后序都可以，递归实现。
>
> 思路三：改进的BFS，不是完全二叉树，而是扩展二叉树的叶子节点为NULL节点。
>
> 思路四：类似于[官方题解方法二](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/er-cha-shu-de-xu-lie-hua-yu-fan-xu-lie-hua-by-le-2/)，用分隔符包装。

{% tabs %}
{% tab title="BFS 超时" %}

```cpp
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    string result;
    if(!root)
        return "[]";
    queue<TreeNode *> pqueue;
    pqueue.push(root);
    while(true){
        bool sign = true;
        int len = pqueue.size();
        for(int i = 0; i < len; i++) {
            TreeNode *ptr = pqueue.front();
            pqueue.pop();
            if (ptr) {
                result.append(to_string(ptr->val));
                result.push_back(',');
                if (ptr->left) {
                    pqueue.push(ptr->left);
                    sign = false;
                } else {
                    pqueue.push(NULL);
                }
                if (ptr->right) {
                    pqueue.push(ptr->right);
                    sign = false;
                } else {
                    pqueue.push(NULL);
                }
            } else {
                result.append("X,");
                pqueue.push(NULL);
                pqueue.push(NULL);
            }
        }
        if(sign)
            break;
    }
    while(!result.empty() && (result.back() == ',' || result.back() == 'X'))
        result.pop_back();
    return "[" + result + "]";
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if(data.size() <= 2)
        return NULL;
    vector<string> tokens;
    string str;
    for(int i = 1; i < data.size() - 1; ++i){
        if(data[i] == 'X'){
            tokens.push_back("X");
            i++;
        }else if(data[i] == ','){
            tokens.push_back(str);
            str.clear();
        }else{
            str.push_back(data[i]);
        }
    }
    tokens.push_back(str);
    int len = tokens.size();
    if(tokens.empty())
        return NULL;
    queue<pair<TreeNode *, int> > iqueue;
    TreeNode *root = new TreeNode(stoi(tokens[0]));
    iqueue.push(make_pair(root, 0));
    while(!iqueue.empty()){
        auto ptr = iqueue.front();
        iqueue.pop();
        int idx = 2 * ptr.second;
        if(idx + 1 < len && tokens[idx + 1] != "X"){
            ptr.first->left = new TreeNode(stoi(tokens[idx + 1]));
            if(2 * (idx + 1) + 1 < len)
                iqueue.push(make_pair(ptr.first->left, idx + 1));
        }
        if(idx + 2 < len && tokens[idx + 2] != "X"){
            ptr.first->right = new TreeNode(stoi(tokens[idx + 2]));
            if(2 * (idx + 2) + 1 < len)
                iqueue.push(make_pair(ptr.first->right, idx + 2));
        }
    }
    return root;
}
```

{% endtab %}
{% endtabs %}

## :pencil2: 4、二叉树遍历之Morris算法

## :pencil2: 5、镜像问题

### 5.1、[**二叉树的镜像**](https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/)

### 5.2、[判断二叉树是不是对称二叉树](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/)

### 5.3、求X节点的个数（阿里面试题）

### 5.4、判断两棵二叉树是否同构

同构是指：两课树可以通过有限次变换左右子树变为同一棵树。如图：

![](/files/-MKQ1uIZXaZqViIeVZmU)

```cpp
bool Isomorphic(TreeNode* t1, TreeNode* t2){
    if(t1 == NULL && t2 == NULL)
        return true;
    if((t1 == NULL) && (t2 != NULL) || ((t1 != NULL) && (t2 == NULL)))
        return false;
    if(t1->val != t2->val)
        return false;
    if((t1->left == NULL) && (t2->left == NULL))
        return Isomorphic(t1->right, t2->right);
    if(((t1->left != NULL) && (t2->left != NULL))
        &&(t1->left->val == t2->left->val))
        //如果两个都不为空且左儿子相等，应该递归的找左对应左，右对应右
        return Isomorphic(t1->left, t2->left) && Isomorphic(t1->right, t2->right);
    else
        //否则就是交换了，递归的判断左对应右，右对应左
        return Isomorphic(t1->left, t2->right) && Isomorphic(t1->right, t2->left);
}
```

## :pencil2: 6、其他

### 6.1、逆时针打印完全二叉树的边界节点

完全二叉树用数组存储，从根节点开始逆时针打印完全二叉树的边界节点。

```cpp
vector<int> BinaryTree::getSeq(int n, vector<int>& tree){
    vector<int> ans;
    if(n == 1){
        ans.push_back(tree[0]);
        return ans;
    }
    // 左边界
    int i = 1;
    while(i - 1 < n){
        ans.push_back(tree[i - 1]);
        i *= 2;
    }
    ans.pop_back();
    // 叶节点
    int j = i / 2 - 2;
    i = i / 2 / 2 - 1;
    for(int k = i; k >= 0 && k < n && k <= j; ++k){
        if(k * 2 + 1 < n)
            ans.push_back(tree[k * 2 + 1]);
        if(k * 2 + 2 < n)
            ans.push_back(tree[k * 2 + 2]);
        if(k * 2 + 1 >= n)
            ans.push_back(tree[k]);
    }
    // 右边界
    while(j > 0){
        ans.push_back(tree[j]);
        j = (j - 2) / 2;
    }
    return ans;
}
```

### 6.2、[**Binary Tree Cameras**](https://leetcode-cn.com/problems/binary-tree-cameras/)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mqjyl2012.gitbook.io/algorithm/leetcode/stick-to-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.