算法

二叉树中的最大路径和

loser

31 Aug 2026 • 9 min read

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。

同一个节点在一条路径序列中至多出现一次。

该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root，返回其最大路径和。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3，路径和为 2 + 1 + 3 = 6。

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7，路径和为 15 + 20 + 7 = 42。

提示：

树中节点数目范围是 [1, 3 * 10^4]
-1000 <= Node.val <= 1000

后序 DFS：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int ans;

public:
    int maxPathSum(TreeNode* root) {
        ans = INT_MIN;
        gain(root);
        return ans;
    }

private:
    int gain(TreeNode* node) {
        if (node == nullptr)
        {
            return 0;
        }

        int leftGain = max(gain(node->left), 0);
        int rightGain = max(gain(node->right), 0);

        int pathSum = node->val + leftGain + rightGain;
        ans = max(ans, pathSum);

        return node->val + max(leftGain, rightGain);
    }
};

核心思想

这题和“二叉树的直径”很像。

路径不一定经过根节点，所以不能只计算从根节点出发的最大路径。

对于任意一个节点，如果最大路径经过这个节点，那么路径可能是：

左子树中的某条向下路径 -> 当前节点 -> 右子树中的某条向下路径

所以需要在每个节点都尝试一次：

node->val + 左侧最大贡献 + 右侧最大贡献

并用它更新全局答案。

这题最关键的观察是：

对当前节点来说，更新全局答案时可以同时使用左右两边；但向父节点返回时，只能选择左边或右边其中一条路径。

原因是路径不能分叉。

如果当前节点要继续接到父节点上，那么这条路径只能是：

父节点 -> 当前节点 -> 左子树某条路径

或者：

父节点 -> 当前节点 -> 右子树某条路径

不能同时带着左右两边一起返回给父节点，否则到父节点后就会形成分叉，不再是一条合法路径。

最大贡献值的含义

定义函数：

int gain(TreeNode* node)

它表示：

从 node 出发，向下走到某个节点，能够提供给 node 父节点的最大路径和

这个值必须包含 node 自己。

并且它只能选择一条向下路径，不能同时选择左子树和右子树。

所以返回值是：

node->val + max(leftGain, rightGain)

其中：

leftGain：左孩子能向当前节点提供的最大贡献
rightGain：右孩子能向当前节点提供的最大贡献

为什么负贡献要丢掉

如果某棵子树的最大贡献是负数，把它接到路径里只会让路径和变小。

例如当前节点值为 20，左子树最大贡献为 15，右子树最大贡献为 -5。

如果强行接上右子树，路径和会减少 5。

所以负贡献不如不选。

代码中写成：

int leftGain = max(gain(node->left), 0);
int rightGain = max(gain(node->right), 0);

这表示：

如果子树贡献为正，就接上它。
如果子树贡献为负，就当作贡献为 0，不接这条分支。

如何更新全局答案

对于当前节点，经过它的最大路径和是：

node->val + leftGain + rightGain

这里可以同时使用左侧和右侧。

因为这条路径的形状是：

左侧某个节点 -> 当前节点 -> 右侧某个节点

它没有分叉，是一条合法路径。

代码中用：

int pathSum = node->val + leftGain + rightGain;
ans = max(ans, pathSum);

更新全局最大路径和。

注意，更新答案和返回贡献是两件不同的事：

更新答案：可以把当前节点当作路径最高点，同时连接左右两边。
返回贡献：只能返回一边给父节点继续使用。

为什么使用后序遍历

计算当前节点的最大路径和，需要先知道左右子树能提供的最大贡献。

也就是说，必须先处理：

左子树
右子树

再处理当前节点。

这正是后序遍历的顺序。

代码中先递归：

int leftGain = max(gain(node->left), 0);
int rightGain = max(gain(node->right), 0);

然后再用左右贡献更新当前节点的路径和。

为什么 `ans` 要初始化为 `INT_MIN`

树中节点值可能全是负数。

例如：

root = [-3]

最大路径至少要包含一个节点，所以答案应该是 -3，而不是 0。

如果把 ans 初始化为 0，就会错误地返回 0。

因此要初始化为：

ans = INT_MIN;

这样即使所有路径和都是负数，也能正确更新到最大的那个节点值。

边界情况

如果二叉树只有一个节点，最大路径就是这个节点本身。

如果所有节点值都是负数，最大路径和就是值最大的那个单独节点。

如果某个子树贡献为负数，算法会把它当作 0，表示不选择这条分支。

如果最大路径完全位于左子树或右子树中，不经过根节点，算法仍然会在递归处理那棵子树时更新全局答案。

如果最大路径经过某个节点并连接它的左右子树，算法会在处理这个节点时用 leftGain + node->val + rightGain 更新答案。

正确性证明

我们证明：算法返回的 ans 等于二叉树中的最大路径和。

结论 1：`gain(node)` 正确返回当前节点能向父节点提供的最大贡献

对于空节点，返回 0，表示没有贡献。

对于非空节点，向父节点提供的路径必须从当前节点出发，并且只能继续走向左子树或右子树中的一边。

如果同时选择左右两边，再接到父节点上，路径就会分叉，不再是一条合法路径。

因此最大贡献只能是：

node->val + max(leftGain, rightGain)

其中负数贡献会被当作 0，表示不选择这条子路径。

所以 gain(node) 的返回值正确。

结论 2：经过当前节点的最大路径和会被正确计算

对于当前节点，如果一条路径以当前节点作为最高连接点，那么它最多可以包含三部分：

左子树向当前节点提供的一条最大贡献路径
当前节点本身
右子树向当前节点提供的一条最大贡献路径

负贡献不会让路径变优，因此可以被丢掉。

所以经过当前节点的最大路径和是：

node->val + leftGain + rightGain

算法正是用这个值更新全局答案。

结论 3：所有可能的最大路径都会被考虑

任意一条合法路径在二叉树中都有一个最高节点。

这个最高节点可能是路径的一端，也可能位于路径中间，连接左右两个方向。

当 DFS 处理到这个最高节点时，路径左右两侧分别位于它的左子树和右子树中，或者只有一侧存在。

根据结论 1，左右子树能提供的最优向下贡献已经被正确计算。

根据结论 2，算法会在这个最高节点处计算包含它的最大路径和。

因此任意可能成为最优解的路径，都会在它的最高节点处被考虑到。

结论 4：算法不会得到非法路径和

每次更新 ans 的路径形态都是：

左侧某条向下路径 -> 当前节点 -> 右侧某条向下路径

其中左侧和右侧都来自当前节点的不同子树，且每边最多选择一条向下路径。

这样的节点序列中不会重复经过同一个节点，也不会产生分叉。

因此每次用于更新 ans 的值都对应一条真实存在的合法路径。

得出结论

由结论 1 可知，递归返回的最大贡献值正确。

由结论 2 可知，每个节点作为路径最高点时的最大路径和计算正确。

由结论 3 可知，所有可能的最优路径都会被考虑，不会遗漏。

由结论 4 可知，算法不会用非法路径更新答案。

因此算法返回的 ans 就是整棵二叉树的最大路径和。

举例理解

以：

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

为例，这棵树可以表示为：

从底向上计算最大贡献：

节点	左贡献	右贡献	经过当前节点的路径和	返回给父节点的贡献
`9`	`0`	`0`	`9`	`9`
`15`	`0`	`0`	`15`	`15`
`7`	`0`	`0`	`7`	`7`
`20`	`15`	`7`	`42`	`35`
`-10`	`9`	`35`	`34`	`25`

最大路径和是 42。

对应路径为：

15 -> 20 -> 7

注意在节点 20 处，更新答案时可以使用左右两边：

15 + 20 + 7 = 42

但节点 20 返回给父节点 -10 的贡献只能选择更大的一边：

20 + max(15, 7) = 35

因为向上接到父节点时，路径不能同时带着左右两条分支。

复杂度分析

设二叉树节点数为 n，树高为 h。

每个节点只会被 DFS 访问一次。

每次访问只进行常数次计算。

所以时间复杂度是：

O(n)

递归调用栈的深度等于树高。

所以空间复杂度是：

O(h)

如果树退化成链，h = n；如果树比较平衡，h = log n。