您的当前位置：首页正文

【hot100】二叉树

来源：步旅网

94. 二叉树中序遍历（迭代做法是重点）

递归解法

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

class Solution {
public:
    vector<int> res;
    void inOrder(TreeNode *root)
    {
        if(!root) return;

        inOrder(root->left);
        res.emplace_back(root->val);
        inOrder(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        inOrder(root);
        return res;
    }
};

普通迭代做法

本质上是用栈来实现对递归的模拟

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

我的代码

错误点

原本树的结构被改变了，这种做法是不那么好的。


class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;  // 用于存储中序遍历结果的向量
        if (!root) return res;  // 如果根节点为空，直接返回空结果

        stack<TreeNode*> st;  // 使用栈来辅助遍历
        st.push(root);  // 将根节点压入栈中

        while (!st.empty()) {  // 当栈不为空时继续循环
            TreeNode *cur = st.top();  // 获取栈顶节点

            if (cur->left) {
                // 如果当前节点有左子节点
                st.push(cur->left);  // 将左子节点压入栈中
                cur->left = nullptr;  // 将当前节点的左子节点设为 nullptr，防止重复访问
            } else {
                st.pop();  // 弹出栈顶节点
                res.emplace_back(cur->val);  // 将当前节点的值添加到结果向量中

                if (cur->right) {
                    // 如果当前节点有右子节点
                    st.push(cur->right);  // 将右子节点压入栈中
                    cur->right = nullptr;  // 将当前节点的右子节点设为 nullptr，防止重复访问
                }
            }
        }

        return res;  // 返回中序遍历结果

力扣题解

本质都是用栈来模拟递归的过程

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;  // 用于存储中序遍历结果的向量
        stack<TreeNode*> stk;  // 使用栈来辅助遍历

        // 主循环，当根节点不为空或栈不为空时继续循环
        while (root != nullptr || !stk.empty()) {
            // 遍历左子树，将所有左子节点依次压入栈中
            while (root != nullptr) {
                stk.push(root);  // 将当前节点压入栈中
                root = root->left;  // 移动到当前节点的左子节点
            }

            // 弹出栈顶节点
            root = stk.top();  // 获取栈顶节点
            stk.pop();  // 弹出栈顶节点

            // 访问当前节点的值，并将其添加到结果向量中
            res.push_back(root->val);

            // 移动到当前节点的右子节点
            root = root->right;
        }

        return res;  // 返回中序遍历结果
    }
};

morris解法

一定要想明白思路，可以去看leetcode的官方题解

时间复杂度：O(n)，其中 n 为二叉树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 O(2n)=O(n)。

空间复杂度：O(1)。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;  // 用于存储中序遍历结果的向量
        TreeNode* preNode = nullptr;  // 记录当前root的直接前驱节点

        while (root) {
            if (root->left) {
                // 如果当前节点有左子节点
                preNode = root->left;  // 初始化前驱节点为当前节点的左子节点
                while (preNode->right && preNode->right != root) {
                    // 找到当前节点左子树中最右边的节点
                    preNode = preNode->right;
                }

                if (preNode->right == nullptr) {
                    // 如果最右边的节点的右子节点为空，说明是第一个访问到该节点，尚未访问root节点的左子树，下面要先去处理root的左子树
                    preNode->right = root;  // 将最右边的节点的右子节点指向当前节点
                    root = root->left;  // 继续遍历左子树
                } else {
                    // 如果最右边的节点的右子节点已经指向当前节点，说明此次是第二次访问，root的左子树已经处理完了
                    res.emplace_back(root->val);  // 访问当前节点的值，处理root的节点
                    preNode->right = nullptr;  // 恢复树的结构
                    root = root->right;  // 继续遍历右子树，去处理root的右子树
                }
            } else {
                // 如果当前节点没有左子节点，要处理root节点
                res.emplace_back(root->val);  // 访问当前节点的值
                root = root->right;  // 继续遍历右子树
            }
        }

        return res;  // 返回中序遍历结果
    }
};

102. 二叉树的层序遍历

广度优先遍历

时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。

灵神代码

只用了一个队列
用 n= q.size（）来控制每次弹出的数目，实现分层的作用

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        if (root == nullptr) return {};
        vector<vector<int>> ans;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            vector<int> vals;
            for (int n = q.size(); n--;) {
                auto node = q.front();
                q.pop();
                vals.push_back(node->val);
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ans.emplace_back(vals);
        }
        return ans;
    }
};

我的代码

用了两个队列，但是不影响时间复杂度和空间复杂度

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> curLevel, nextLevel;
        int level  = 0;
        vector<vector<int>> res;
        if(!root) return res;

        curLevel.push(root);

        while(!curLevel.empty())
        {
            vector<int> curLevelVec;
            while(!curLevel.empty())
            {
                TreeNode* curNode = curLevel.front();
                curLevelVec.emplace_back(curNode->val);
                curLevel.pop();

                if(curNode->left) nextLevel.push(curNode->left);
                if(curNode->right) nextLevel.push(curNode->right);
            }

            res.emplace_back(move(curLevelVec));
            curLevel = move(nextLevel);
        }

        return res;
    }
};

104. 二叉树的最大深度

递归做法—深度优先搜索

时间复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度：O(height)，其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

题解代码：优雅！

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

我的代码

class Solution {
public:
    int res=0;
    void maxDepth(TreeNode* root, int depth)
    {
        if(!root->left && !root->right )  res = max(res,depth);
        if(root->left) maxDepth(root->left,depth+1);
        if(root->right) maxDepth(root->right,depth+1);
    }
    int maxDepth(TreeNode* root) {

        if(!root) return res;
        maxDepth(root,1);
        return res;
    }
};

226. 翻转二叉树

递归解法

时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。

空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

我的代码

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 如果根节点为空，直接返回 nullptr
        if (!root) return nullptr;

        // 递归翻转右子树
        TreeNode* curLeft = invertTree(root->right);
        // 递归翻转左子树
        TreeNode* curRight = invertTree(root->left);

        // 交换左右子树
        root->left = curLeft;
        root->right = curRight;

        // 返回当前节点
        return root;
    }
};

101. 对称二叉树

递归做法

时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }
};

迭代做法

时间复杂度：O(n)，同「方法一」。
空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。

class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || (u->val != v->val)) return false;

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

543. 二叉树的直径

递归做法

时间复杂度：O(N)，其中 N 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
空间复杂度：O(Height)，其中 Height 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为 O(Height) 。

我的代码

需要注意的是，最长的直径不一定过根节点

class Solution {
public:

    int res=0;
    int maxDepth(TreeNode *root)
    {
        if(!root) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);

        res = max(res,right+left);
        return max(left,right)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {

        maxDepth(root);
        return res;
    }
};

108. 将有序数组转换为二叉搜索树

我的代码

时间复杂度：O(n)，其中 n 是数组的长度。每个数字只访问一次。
空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(logn)。

class Solution {
public:
    // 辅助函数，将有序数组转换为平衡二叉搜索树
    TreeNode* sortedArrayToBST(vector<int>& nums, int i, int j) // j 不算在内
    {
        int n = j - i;  // 计算区间长度
        if (n <= 0) return nullptr;  // 如果区间长度小于等于0，返回 nullptr

        int m = (i + j) / 2;  // 计算中间索引
        TreeNode *root = new TreeNode(nums[m]);  // 创建中间节点作为根节点

        // 递归构建左子树
        root->left = sortedArrayToBST(nums, i, m);

        // 递归构建右子树
        root->right = sortedArrayToBST(nums, m + 1, j);

        return root;  // 返回构建好的根节点
    }

    // 主函数，将有序数组转换为平衡二叉搜索树
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums, 0, nums.size());  // 调用辅助函数，初始区间为 [0, nums.size())
    }
};

98. 验证二叉搜索树(未作出来)

递归做法

时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。

官方题解

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

中序遍历（morris 空间复杂度更优秀）

时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。
空间复杂度：O(1)。

class Solution {
public:
    bool isValidBST(TreeNode* root) {

        long long lastVal = LONG_MIN;
        TreeNode* preNode = nullptr; // 记录当前root的直接前驱节点
        bool flag = 1;
        while (root) {
            if (root->left) {
                // 如果当前节点有左子节点
                preNode = root->left; // 初始化前驱节点为当前节点的左子节点
                while (preNode->right && preNode->right != root) {
                    // 找到当前节点左子树中最右边的节点
                    preNode = preNode->right;
                }

                if (preNode->right == nullptr) {
                    // 如果最右边的节点的右子节点为空，说明是第一个访问到该节点，尚未访问root节点的左子树，下面要先去处理root的左子树
                    preNode->right =
                        root;          // 将最右边的节点的右子节点指向当前节点
                    root = root->left; // 继续遍历左子树
                } else {
                    // 如果最右边的节点的右子节点已经指向当前节点，说明此次是第二次访问，root的左子树已经处理完了
                    if (root->val <= lastVal) {
                        flag = 0;
                    }

                    lastVal = root->val;
                    preNode->right = nullptr; // 恢复树的结构
                    root = root->right; // 继续遍历右子树，去处理root的右子树
                }
            } else {
                // 如果当前节点没有左子节点，要处理root节点
                if (root->val <= lastVal) {
                    flag = 0;
                }

                lastVal = root->val;
                root = root->right; // 继续遍历右子树
            }
        }

        return flag; // 返回中序遍历结果
    }
};

230. 二叉搜索树中第k小的元素

递归解法

时间复杂度：O(n)，其中 n 是二叉树的大小（节点个数）。
空间复杂度：O(h)，其中 h 是树高，递归需要 O(h) 的栈空间。最坏情况下树是一条链，h=n，空间复杂度为 O(n)。

我的代码

class Solution {
public:

    int func(TreeNode* root, int &k)
    {
        // 如果当前节点为空，说明已经到达树的末端，返回 -1 表示未找到。
        if (!root) return -1;

        // 递归调用左子树，尝试在左子树中找到第 k 小的元素。
        int leftRes = func(root->left, k);
        // 如果在左子树中找到了结果（非 -1），直接返回该结果。
        if (leftRes != -1) return leftRes;
        
        // 访问根节点，每访问一个节点，k 减 1。
        k--;
        // 如果此时 k 减到了 0，说明当前节点就是要找的第 k 小的元素。
        if (k == 0) return root->val;

        // 如果左子树和当前节点都不是要找的元素，则递归右子树。
        return func(root->right, k);
    }

    int kthSmallest(TreeNode* root, int k) {

        // 调用辅助函数，并返回其结果。
        return func(root, k);
        
    }
};

迭代解法(morris算法也可以解)

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {

        TreeNode* preNode = nullptr; // 记录当前root的直接前驱节点
        int res = -1;
        while (root) {
            if (root->left) {
                // 如果当前节点有左子节点
                preNode = root->left; // 初始化前驱节点为当前节点的左子节点
                while (preNode->right && preNode->right != root) {
                    // 找到当前节点左子树中最右边的节点
                    preNode = preNode->right;
                }

                if (preNode->right == nullptr) {
                    // 如果最右边的节点的右子节点为空，说明是第一个访问到该节点，尚未访问root节点的左子树，下面要先去处理root的左子树
                    preNode->right =
                        root;          // 将最右边的节点的右子节点指向当前节点
                    root = root->left; // 继续遍历左子树
                } else {
                    // 如果最右边的节点的右子节点已经指向当前节点，说明此次是第二次访问，root的左子树已经处理完了

                    k--;
                    if(k == 0) res = root->val; 
                    preNode->right = nullptr; // 恢复树的结构
                    root = root->right; // 继续遍历右子树，去处理root的右子树
                }
            } else {
                // 如果当前节点没有左子节点，要处理root节点
                k--;

                if(k == 0) 
                {
                    res = root->val; 
                }
                root = root->right; // 继续遍历右子树
            }
        }

        return res; // 返回中序遍历结果
    }
};

进阶题答案

199. 二叉树的右视图

递归写法

时间复杂度：O(n)，其中 n 是二叉树的节点个数。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归需要 O(h) 的栈空间。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。

我的代码

总体思路，就是先看左边，最后看右边，这样右边的节点会是最后更新节点的

class Solution {
public:
    vector<int> res; // 用于存储从右侧视角看到的节点值

    void func(TreeNode* root, int depth) {
        if (!root)
            return; // 如果当前节点为空，则直接返回

        // 递归遍历左子树，增加深度
        func(root->left, depth + 1);

        // 确保 res 的大小至少为 depth，如果不足则添加0作为占位符
        while (depth > res.size()) {
            res.emplace_back(0);       
        }

        // 更新对应深度位置的值为当前节点的值
        // 注意这里使用的是 depth-1 因为数组索引是从0开始的
        res[depth-1] = root->val;

        // 递归遍历右子树，增加深度
        func(root->right, depth + 1);
    }

    vector<int> rightSideView(TreeNode* root) {
        // 调用辅助函数，从根节点开始，初始深度为1
        func(root, 1);
        // 返回结果
        return res;
    }
};

灵神代码

先看右边，当第一次到达某个深度的时候，放入ans中

class Solution {
    vector<int> ans;

    void dfs(TreeNode* node, int depth) {
        if (node == nullptr) {
            return;
        }
        if (depth == ans.size()) { // 这个深度首次遇到
            ans.push_back(node->val);
        }
        dfs(node->right, depth + 1); // 先递归右子树，保证首次遇到的一定是最右边的节点
        dfs(node->left, depth + 1);
    }

public:
    vector<int> rightSideView(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
};

114. 二叉树展开为链表

原地解法

题解代码

错误点：这里处理后的节点的左指针置空，一定不能忘记
// 当前节点的左子指针置空
curr->left = nullptr;
这题的解法和morris 中序的方法十分相似，可以对照理解

class Solution {
public:
    // 将二叉搜索树转换为单右子树结构（即只包含右子节点的链表形式）
    void flatten(TreeNode* root) {
        TreeNode *curr = root;
        // 遍历整棵树，直到所有节点都处理完毕
        while (curr != nullptr) {
            // 如果当前节点有左子树，则需要调整结构
            if (curr->left != nullptr) {
                // next指向当前节点的左子节点
                auto next = curr->left;
                // 找到左子树中的最右节点（即前驱节点）
                auto predecessor = next;
                while (predecessor->right != nullptr) {
                    predecessor = predecessor->right;
                }
                // 将当前节点的右子树挂到前驱节点的右子树上
                predecessor->right = curr->right;
                // 当前节点的左子指针置空
                curr->left = nullptr;
                // 将当前节点的左子树变为右子树
                curr->right = next;
            }
            // 移动到下一个节点继续处理
            curr = curr->right;
        }
    }
};

头插法

时间复杂度：O(n)，其中 n 是二叉树的节点个数。
空间复杂度：O(n)。递归需要 O(n) 的栈空间。

灵神代码

class Solution {
    TreeNode* head;
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        flatten(root->right);
        flatten(root->left);
        root->left = nullptr;
        root->right = head; // 头插法，相当于链表的 root->next = head
        head = root; // 现在链表头节点是 root
    }
};

分治

时间复杂度：O(n)，其中 n 是二叉树的节点个数。
空间复杂度：O(n)。递归需要 O(n) 的栈空间。

灵神代码

class Solution {
    TreeNode* dfs(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left_tail = dfs(root->left);
        TreeNode* right_tail = dfs(root->right);
        if (left_tail) {
            left_tail->right = root->right; // 左子树链表 -> 右子树链表
            root->right = root->left; // 当前节点 -> 左右子树合并后的链表
            root->left = nullptr;
        }
        return right_tail ? right_tail : left_tail ? left_tail : root;
    }

public:
    void flatten(TreeNode* root) {
        dfs(root);
    }
};

105. 从前序与中序遍历序列构造二叉树

哈希表+递归

时间复杂度：O(n)，其中 n 为 preorder 的长度。递归 O(n) 次，每次只需要 O(1) 的时间。
空间复杂度：O(n)。

灵神代码

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        index = {x: i for i, x in enumerate(inorder)}

        def dfs(pre_l: int, pre_r: int, in_l: int, in_r: int) -> Optional[TreeNode]:
            if pre_l == pre_r:  # 空节点
                return None
            left_size = index[preorder[pre_l]] - in_l  # 左子树的大小
            left = dfs(pre_l + 1, pre_l + 1 + left_size, in_l, in_l + left_size)
            right = dfs(pre_l + 1 + left_size, pre_r, in_l + 1 + left_size, in_r)
            return TreeNode(preorder[pre_l], left, right)

        return dfs(0, len(preorder), 0, len(inorder))  # 左闭右开区间

437. 路径总和 III

哈希表+递归

时间复杂度：O(n)，其中 n 是二叉树的节点个数。
空间复杂度：O(n)。

我的代码

class Solution {

private:
    unordered_map<long long, int> mp;

public:
    int pathSum(TreeNode* root, long long curr, int targetSum) {
        if (!root)
            return 0;

        int ret = 0;
        curr += root->val;

        if (mp.count(curr - targetSum)) {
            ret += mp[curr - targetSum];
        }

        mp[curr]++;
        ret += pathSum(root->left, curr, targetSum);
        ret += pathSum(root->right, curr, targetSum);
        mp[curr]--;

        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {

        mp[0] = 1;
        return pathSum(root, 0, targetSum);
    }
};

236. 二叉树的最近公共祖先

递归

时间复杂度：O(n)，其中 n 为二叉树的节点个数。
空间复杂度：O(n)。最坏情况下，二叉树是一条链，因此递归需要 O(n) 的栈空间

我的代码

class Solution {
private:
    TreeNode* res = nullptr;

public:
    int func(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root)
            return 0;

        int ret = 0;
        ret += func(root->left, p, q);
        ret += func(root->right, p, q);
        if (root == p || root == q)
            ret++;

        if (ret == 2 && res == nullptr)
            res = root;

        return ret;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        func(root, p, q);
        return res;
    }
};

灵神代码：优雅

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right) { // 左右都找到
            return root; // 当前节点是最近公共祖先
        }
        return left ? left : right;
    }
};

124. 二叉树中的最大路径和

递归写法

时间复杂度：O(N)，其中 N 是二叉树中的节点个数。对每个节点访问不超过 2 次。
空间复杂度：O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。

class Solution {
private:
    int maxGain(TreeNode* node) {
        if (node == nullptr) return 0;

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于0时，才会选取对应子节点
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node->val + leftGain + rightGain;

        // 更新答案
        res = max(res, priceNewpath);

        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);
    }

public:
    int res = INT_MIN;
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return res;
    }
};

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文