Binary Tree Maximum Path Sum
这道题和普通的二叉树遍历题不太一样。 前面的很多题，可能只是让你：
-
求深度
-
判断是否合法
-
做前中后序遍历
-
统计节点数量
但这道题要求的是：
在整棵二叉树中，找到一条路径，使这条路径上的节点值之和最大。
这就意味着，我们不能只盯着“从根到叶子”的路径，也不能只盯着某一个方向。 因为题目中的路径可以：
-
从某个节点出发
-
向上经过父节点
-
再走到另一侧子树
也就是说，这条路径完全可能是：
左子树 -> 当前节点 -> 右子树
而这，正是这道题最核心、也最容易让人绕晕的地方。
树形递归 + 维护单边贡献值 + 全局更新答案
本文就系统讲清楚这道题到底在求什么、为什么递归返回值要这么设计，以及 ans 为什么要单独作为全局变量来维护。
题目介绍
给定一棵二叉树的根节点 root，请你返回这棵树中的最大路径和。
这里的“路径”有几个非常重要的特点：
-
路径中的节点必须是连通的
-
每个节点在路径中最多出现一次
-
路径不一定经过根节点
-
路径至少包含一个节点
也就是说，路径不要求从根开始，也不要求到叶子结束。 只要是一条沿着父子关系连起来的连续路径，就算合法。
例如下面这棵树：
1
/ \
2 3
最大路径和是：
2 + 1 + 3 = 6
因为最优路径就是：
2 -> 1 -> 3
示例
示例 1
输入：
root = [1,2,3]
输出：
6
对应二叉树：
1
/ \
2 3
最大路径是：
2 -> 1 -> 3
路径和为 6。
示例 2
输入：
root = [-10,9,20,null,null,15,7]
输出：
42
对应二叉树：
-10
/ \
9 20
/ \
15 7
最大路径是：
15 -> 20 -> 7
路径和为：
15 + 20 + 7 = 42
注意这里的最优路径并没有经过根节点 -10。 这也是这道题最容易忽略的一点。
这道题难在哪里？
很多人第一次看到这题时，最容易下意识想到的是：
能不能求每个节点到叶子的最大路径和？
但很快会发现不对，因为这题要求的不是“单边路径”，而是整棵树中的任意路径。
比如某条最大路径可能长这样：
左边一条链 -> 当前节点 -> 右边一条链
这意味着：
-
对于某个节点来说，它有可能同时使用左子树和右子树
-
但如果这个值要返回给父节点时，却不能左右两边都带上
因为路径一旦返回给父节点，还要继续往上延伸。 而一条合法路径不能在某个节点处分叉成三条路。
所以这道题真正的难点就在于：
“当前节点作为路径最高点时的答案” 和 “当前节点向父节点提供的最大贡献值”
这两个东西不是同一个概念。
只要把这两个概念分清楚，这题就通了。
核心思路
对于每一个节点，我们实际上要思考两件事：
第一件事：如果把当前节点当作路径的“拐点”或“最高点”，最大路径和是多少？
也就是：
左边贡献 + 当前节点值 + 右边贡献
这条路径在当前节点这里“收口”，不会再继续往上延伸。
它的作用是：
用来更新整棵树的最终答案。
第二件事：如果当前节点要把路径继续往上交给父节点，它最多能提供多少贡献？
因为父节点如果还要接这条路径，只能从当前节点这里选一边继续往上走：
-
要么走左边
-
要么走右边
-
不可能左右都带上
所以返回给父节点的值只能是：
当前节点值 + max(左贡献, 右贡献)
但如果某一边贡献是负数，那么带上它反而会让路径变差。 所以还要和 0 比较，负贡献直接舍弃。
于是递归返回值就变成了：
max(当前节点值 + max(左贡献, 右贡献), 0)
这就是你代码里最后那句返回语句的含义。
Java 代码
class Solution {
private int ans = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return ans;
}
private int dfs(TreeNode node) {
if (node == null) {
return 0;
}
int lVal = dfs(node.left);
int rVal = dfs(node.right);
ans = Math.max(ans, lVal + rVal + node.val);
return Math.max(Math.max(lVal, rVal) + node.val, 0);
}
}
这段代码不长，但信息量非常大。 其中最关键的地方有两个：
-
ans = Math.max(ans, lVal + rVal + node.val); -
return Math.max(Math.max(lVal, rVal) + node.val, 0);
一个负责更新全局最大路径和。 一个负责返回当前节点对父节点的最大贡献。
代码拆解
下面一部分一部分来看。
1. 为什么要有一个全局变量 ans？
private int ans = Integer.MIN_VALUE;
这个变量表示：
整棵树当前找到的最大路径和。
为什么它必须是全局变量？
因为我们在递归过程中，遍历到每一个节点时，都有可能发现一条更优路径。 而这条路径不一定会被递归返回给上层。
比如：
15 -> 20 -> 7
这条路径会在节点 20 这里被计算出来，但它不会作为一个完整路径继续返回给 -10。 因为返回给父节点时只能返回单边贡献，而不能把左右两边一起带上。
所以：
-
“完整路径和”只能用来更新全局答案
-
“单边最大贡献”才是递归返回值
这就是 ans 存在的原因。
另外，初始值设成 Integer.MIN_VALUE 也很重要。 因为树中的节点值可能全是负数，如果初始值设成 0，就会出错。
2. maxPathSum 函数在做什么？
public int maxPathSum(TreeNode root) {
dfs(root);
return ans;
}
这个函数非常简单：
-
通过
dfs(root)遍历整棵树 -
在遍历过程中不断更新
ans -
最后返回全局最优结果
也就是说，真正的逻辑都在 dfs 里面。
3. 为什么空节点返回 0？
if (node == null) {
return 0;
}
这表示：
空节点对路径没有贡献。
因为路径和本质上是节点值相加，空节点不存在，自然贡献为 0。
这样写还有一个好处，就是递归逻辑会非常统一：
-
左子树不存在，就返回
0 -
右子树不存在，就返回
0
后面直接拿来计算即可。
4. lVal 和 rVal 分别表示什么？
int lVal = dfs(node.left);
int rVal = dfs(node.right);
这里的 lVal 和 rVal，并不是“左子树的最大路径和”“右子树的最大路径和”。
它们表示的是：
左孩子 / 右孩子能够向当前节点提供的最大单边贡献值。
注意这个定义很重要。 它不是某棵子树内部的完整答案，而是“如果我要经过这个孩子继续往下走，最多能拿到多少收益”。
比如某个节点左边有一条很优的路径，但它如果已经在左子树内部形成了一个完整拐点路径，那部分不会整个返回上来。 返回上来的只能是一条单链。
5. 为什么更新答案用 lVal + rVal + node.val？
ans = Math.max(ans, lVal + rVal + node.val);
因为这代表的是：
以当前节点为最高点时，能形成的最大路径和。
路径长这样：
左边一条贡献链 -> 当前节点 -> 右边一条贡献链
所以和就是：
左贡献 + 当前节点值 + 右贡献
这一步非常关键，因为整棵树中的最大路径，很可能就是在某个节点这里“左 + 中 + 右”拼出来的。
例如：
1
/ \
2 3
在节点 1 这里：
-
左贡献是
2 -
右贡献是
3 -
当前节点值是
1
所以路径和就是：
2 + 1 + 3 = 6
这正是答案。
6. 为什么返回值只能选一边？
return Math.max(Math.max(lVal, rVal) + node.val, 0);
这是整道题最核心的地方。
当前节点如果要把贡献继续传给父节点，那么路径只能沿着一条分支往上走。 因为父节点如果再接上来，就已经形成更长的一条链了。
这时候如果你把左右两边都返回给父节点，相当于路径在当前节点发生了分叉。 那就不是一条合法路径了。
所以返回值只能是：
当前节点值 + max(左贡献, 右贡献)
表示“从当前节点出发，向下一路延伸，最多能提供多少收益”。
但是，如果这条贡献值是负数呢？
比如：
-
左子树很差
-
带上它反而让路径和变小
那还不如不要。 所以最后还要和 0 比较：
max(当前节点值 + max(左贡献, 右贡献), 0)
这表示：
-
如果带上某一边有收益，就带上
-
如果没有收益，就干脆从当前节点这里截断
手动模拟一遍
我们用经典例子来完整走一遍：
root = [-10,9,20,null,null,15,7]
二叉树结构是：
-10
/ \
9 20
/ \
15 7
第一步：处理节点 15
节点 15 左右都是空节点。
所以：
lVal = 0
rVal = 0
更新答案：
ans = max(-∞, 0 + 0 + 15) = 15
返回给父节点的贡献值：
max(max(0, 0) + 15, 0) = 15
第二步：处理节点 7
同理：
lVal = 0
rVal = 0
更新答案：
ans = max(15, 0 + 0 + 7) = 15
返回贡献值：
7
第三步：处理节点 20
此时：
-
左贡献
lVal = 15 -
右贡献
rVal = 7
更新答案：
ans = max(15, 15 + 7 + 20) = 42
这说明以 20 为最高点时，形成了一条很优路径：
15 -> 20 -> 7
返回给父节点的贡献值只能选一边：
max(max(15, 7) + 20, 0) = 35
也就是说，节点 20 最多向上提供 35 的收益，对应路径：
20 -> 15
或者写成从下往上看就是：
15 -> 20
第四步：处理节点 9
同理：
lVal = 0
rVal = 0
更新答案：
ans = max(42, 9) = 42
返回贡献值：
9
第五步：处理根节点 -10
现在：
-
左贡献
lVal = 9 -
右贡献
rVal = 35
更新答案：
ans = max(42, 9 + 35 - 10) = 42
也就是说，经过根节点的路径和是：
9 + (-10) + 35 = 34
它并没有超过之前在节点 20 处得到的 42。
所以最终答案仍然是：
42
为什么全是负数时也成立？
比如这棵树：
-3
递归到节点 -3 时：
-
左贡献 =
0 -
右贡献 =
0
更新答案：
ans = max(-∞, -3) = -3
返回值：
max(-3, 0) = 0
虽然返回给父节点的是 0，但全局答案已经被正确更新成 -3 了。
这也是为什么：
-
返回值可以和
0比较 -
但
ans必须初始化成负无穷
否则全负数情况就会出错。
这道题真正想考什么？
这道题表面上是在求最大路径和，但本质上考察的是：
树形递归中，如何区分“子问题返回值”和“全局答案”。
第一，是否理解递归返回值的含义
很多树题最难的地方，不是递归本身，而是：
递归函数到底应该返回什么？
这题中，dfs(node) 返回的不是“以 node 为根的最大路径和”，而是：
node 作为一条单边路径起点时，能向父节点提供的最大贡献值。
这个定义一旦想清楚，代码就顺了。
第二，是否理解“经过当前节点的完整答案”和“向上延伸的局部贡献”是不同的
这题最容易混淆的就是这两者。
-
lVal + rVal + node.val：是当前节点作为拐点时的完整路径和 -
max(lVal, rVal) + node.val：是当前节点能向上返回的单边贡献
前者拿来更新答案。 后者拿来参与递归。
它们不能混为一谈。
第三，是否会处理负贡献
如果某棵子树返回的是负值，说明带上它只会拖后腿。 那就应该直接舍弃。
所以返回值和 0 比较，是这道题非常关键的一步。
这其实也是很多“最大路径”“最大收益”问题里常见的处理方式：
负贡献直接截断。
复杂度分析
假设二叉树一共有 n 个节点。
时间复杂度
每个节点都会被访问一次，每次只进行常数级计算，所以时间复杂度是：
O(n)
空间复杂度
空间主要来自递归调用栈。
-
如果树比较平衡，递归深度大约是
O(log n) -
如果树退化成链表，递归深度最坏是
O(n)
所以空间复杂度可以写成：
O(h)
其中 h 是树的高度。 最坏情况下是：
O(n)
这题和“二叉树的最大深度”有什么不同？
它们都用递归，但思想差别很大。
最大深度
最大深度这类题，递归返回值往往就是问题本身：
当前节点的最大深度 = max(左深度, 右深度) + 1
最大路径和
这题不是。 因为“完整路径答案”可能在当前节点这里左右同时展开，但返回给父节点时又不能两边都带上。
所以这题多了一层区分：
-
一个值用于更新全局答案
-
一个值用于递归返回
这也是它比普通树题更难的原因。
总结
这道题的核心思想可以概括成一句话：
递归计算每个节点向父节点提供的最大单边贡献，同时把“左贡献 + 当前节点 + 右贡献”作为经过当前节点的完整路径和，用来更新全局最大答案。
具体步骤就是：
-
递归得到左右子树对当前节点的最大贡献值
-
用
左贡献 + 右贡献 + 当前节点值更新全局答案 -
返回
当前节点值 + max(左贡献, 右贡献)作为单边贡献 -
如果单边贡献小于
0，就直接返回0
是一道非常经典的树形 DP / 树形递归题。 真正吃透它之后，你会更容易理解很多后续题目里的共同套路：
-
递归函数返回的未必是最终答案
-
局部最优值和全局最优值可能要分开维护
-
负贡献要及时截断
-
树上的路径问题，经常要区分“单边延伸”和“当前成环节点评估”
把这道题真正理解透，再去看很多二叉树路径类问题时，你会明显更容易抓住递归定义。
