二叉树中的最大路径和 图解题解

这道题到底在问什么

root

[-10,9,20,null,null,15,7]

输出

42

最优解：一步一步想明白

1. 3关键不是背模板，而是看懂为什么这题适合二叉树 · 树形 DP。
2. 4后序先算左贡献树形 DP 用后序遍历：要先拿到左右子树的结果，才能算当前节点。所以先深入左子树 9，算出它能向上贡献多少。
3. 5负贡献不要，直接当 0拿到子树贡献后先过一道闸：如果是负数，接上它只会让路径和更小，于是用 max(0, 贡献) 直接当 0——相当于这一支不要了。
4. 6再算右贡献同样地深入右子树，算出右边能向上贡献的最大值(同样负的就当 0)。左右贡献都拿到了，才轮到处理当前节点。
5. 7穿过当前节点的路径 = 左 + val + 右先处理右子树的根 20。穿过 20 的路径可以从左拐到 15、再从右拐到 7，所以穿过值 = 15 + 20 + 7 = 42。这是「在 20 这里拐了个弯」的路径。
6. 8用穿过值更新全局答案这个穿过值 42 可能就是最终答案，所以用它去更新全局最大值。注意：它只更新答案，并不往上返回——拐过弯的路不能再接给父亲。
7. 9返回给父亲时只能选一边现在轮到把结果返回给父亲 -10。父亲要把 20 这一支接成一条不分叉的直路，所以 20 只能保留左右里更大的一边，不能左右都要。
8. 10返回 val + max(左,右)于是返回值 = 20 + max(左15, 右7) = 35，把较大的左边 15 接上。穿过值 42 用来更新答案、返回值 35 交给父亲——同一个节点，两个不同的值。
9. 11根处理完，全局答案是 42回到根 -10：左贡献 max(0,9)=9、右贡献 max(0,35)=35，穿过根 = 9+(-10)+35 = 34，没超过 42。所有节点都比过一遍后，全局答案定格在 42，也就是路径 15→20→7。
10. 12穿过值更新答案(可左拐右拐) ≠ 返回值给父亲(只能选一边)这是树形 DP 最难、最容易写错的一帧：每个节点要算两个不同的值。第一个是「穿过它的路径」，可以从左孩子拐上来、再拐到右孩子，等于 15 + 20 + 7 = 42——它能成为答案，因为一条路径允许在某个节点拐一次弯。第二个是「返回给父亲的值」，父亲要把它接成一条直路、不能分叉，所以只能选 20 加上左右里更大的一边 = 35。把这两个值搞混，就是这题最大的坑。
11. 15把这句话记住，下次遇到同类题，就能更快选出方向。
12. 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def maxPathSum(self, root):
        ans = -10**18
        def dfs(node):
            nonlocal ans
            if not node:
                return 0
            left = max(0, dfs(node.left))
            right = max(0, dfs(node.right))
            ans = max(ans, left + node.val + right)
            return node.val + max(left, right)
        dfs(root)
        return ans

class Solution {
    int ans = INT_MIN;
    int dfs(TreeNode* root) {
        if (!root) return 0;
        int left  = max(0, dfs(root->left));   // 负贡献丢弃
        int right = max(0, dfs(root->right));
        ans = max(ans, left + root->val + right); // 穿过更新答案
        return root->val + max(left, right);      // 返回只选一边
    }
public:
    int maxPathSum(TreeNode* root) { dfs(root); return ans; }
};

class Solution {
    int ans = Integer.MIN_VALUE;
    int dfs(TreeNode root) {
        if (root == null) return 0;
        int left  = Math.max(0, dfs(root.left));   // 负贡献丢弃
        int right = Math.max(0, dfs(root.right));
        ans = Math.max(ans, left + root.val + right); // 穿过更新答案
        return root.val + Math.max(left, right);      // 返回只选一边
    }
    public int maxPathSum(TreeNode root) { dfs(root); return ans; }
}

# 二叉树 · 树形 DP 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界

class Solution {
    int ans = INT_MIN;
    int dfs(TreeNode* root) {
        if (!root) return 0;
        int left  = max(0, dfs(root->left));   // 负贡献丢弃
        int right = max(0, dfs(root->right));
        ans = max(ans, left + root->val + right); // 穿过更新答案
        return root->val + max(left, right);      // 返回只选一边
    }
public:
    int maxPathSum(TreeNode* root) { dfs(root); return ans; }
};

class Solution {
    int ans = Integer.MIN_VALUE;
    int dfs(TreeNode root) {
        if (root == null) return 0;
        int left  = Math.max(0, dfs(root.left));   // 负贡献丢弃
        int right = Math.max(0, dfs(root.right));
        ans = Math.max(ans, left + root.val + right); // 穿过更新答案
        return root.val + Math.max(left, right);      // 返回只选一边
    }
    public int maxPathSum(TreeNode root) { dfs(root); return ans; }
}

复杂度

面试官可能追问