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

这道题的路径和直觉里的不一样

这里的「路径」是树中任意一串相邻相连的节点：不必经过根、不必到叶子、可以在某个节点处拐弯（一头来自左子树、一头来自右子树），但不能分叉成三条。节点值可正可负，路径至少含一个节点。要求所有合法路径里节点值之和的最大值。「可负」和「不必过根」这两点，决定了它比求直径（LeetCode 543）多一层裁剪逻辑。

为什么按最高拐点枚举就不重不漏

路径的形状有个不变的骨架：任何一条路径都存在唯一一个位置最高的节点，路径在它这里拐弯，两头分别沿左、右子树往下延伸（某一头可以为空）。于是把所有路径按「最高拐点是谁」分类——每个节点当一次拐点，算出以它为拐点能拼出的最大路径和，取全局最大，就必然覆盖所有路径且互不重复。以节点 x 为拐点的最优值是 x.val + L + R，其中 L、R 分别是左右孩子往下延伸的最大单边和。这类在树上自底向上递推的做法通常叫树形 DP。

为什么返回给父亲的是单边而不是左加右

递归函数 gain(node) 要给父亲一个数：从父亲走进 node 之后，往下最多还能捞多少分。路径进了 node 只能继续沿一条腿往下走——若左右都走就在 node 处拐了弯，而拐点已经是 node，这条路径不可能再向上延伸到父亲。所以返回值只能是 node.val + max(L, R)，即挑更肥的那条腿。

而 node.val + L + R 是把两条腿都接上的「拐弯路径」，它是 node 作为拐点的完整答案，只能就地和全局最大值比较，不能上传。一个函数、两个口径——返回单边、全局收拐弯值——是这套套路的核心，混用任何一个都错。

负贡献为什么要裁成零

路径有权「不要」某条子分支：如果一条腿往下走的最大和是负数，接上它只会拖累总和，最优选择就是不走这条腿，等价于让它贡献 0。所以代码里读孩子返回值时先做 L = max(0, gain(node.left))、R 同理。这一步是本题与求直径最大的差别——直径里边数不会为负，不需要裁剪；本题节点值可负，不裁剪就会把明明可以舍弃的负分强行算进来。

答案初值为什么必须是负无穷

全局答案 ans 的初值要设成负无穷而不是 0。因为路径至少要含一个节点，当整棵树全是负数时（比如只有一个值为 -3 的节点），正确答案是 -3；初值若是 0，它比任何真实路径和都大，会错误地输出 0。设成负无穷后，每个节点的拐弯值 node.val + L + R 至少会以「只含自己」的形式参与一次比较（此时 L、R 被裁成 0），全负树也能得到正确的最大单点值。

复杂度与同构题

时间 O(n)：后序遍历中每个节点恰好访问一次，每次只做常数次比较与加法。空间 O(h)：递归栈深度等于树高，最坏退化成链是 O(n)。

「返回单边链、全局更新拼接值」这套骨架能直接套到一批题上：二叉树的直径（LeetCode 543）是边数版，最长同值路径（LeetCode 687）是加约束版；本题是在骨架上叠加 max(0, …) 处理负值。骨架吃透，这一族题只剩口径差异。

Python

class Solution:
    def maxPathSum(self, root):
        self.ans = float("-inf")
        def gain(node):
            if not node: return 0
            L = max(0, gain(node.left))   # 负贡献裁成 0
            R = max(0, gain(node.right))
            self.ans = max(self.ans, node.val + L + R)  # 穿过本节点
            return node.val + max(L, R)   # 返回单边贡献
        gain(root)
        return self.ans

C++

class Solution {
    int ans = INT_MIN;
    int gain(TreeNode* node){
        if(!node) return 0;
        int L = max(0, gain(node->left));   // 负贡献裁成 0
        int R = max(0, gain(node->right));
        ans = max(ans, node->val + L + R);  // 穿过本节点
        return node->val + max(L, R);       // 返回单边贡献
    }
public:
    int maxPathSum(TreeNode* root){
        gain(root);
        return ans;
    }
};

Java

class Solution {
    private int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        gain(root);
        return ans;
    }
    private int gain(TreeNode node) {
        if (node == null) return 0;
        int L = Math.max(0, gain(node.left));   // 负贡献裁成 0
        int R = Math.max(0, gain(node.right));
        ans = Math.max(ans, node.val + L + R);  // 穿过本节点的路径
        return node.val + Math.max(L, R);       // 返回给父亲的单边贡献
    }
}