05、二叉树的最大路径和
大约 6 分钟数据结构算法算法基地面试深搜广搜二叉树刷题
哈喽，大家好，我是厨子，今天给大家分享一个经典题目
https://leetcode.cn/problems/binary-tree-maximum-path-sum/
题目描述
二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。
同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和。
给你一个二叉树的根节点 root，返回其最大路径和。
示例 1:
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
1
/ \
2 3
示例 2:
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
-10
/ \
9 20
/ \
15 7
约束条件:
- 树中节点数目范围是
[1, 3 * 10^4] -1000 <= Node.val <= 1000
什么是路径？
路径的定义
路径特点：
1. 至少包含一个节点
2. 节点至多出现一次
3. 相邻节点之间有边连接
4. 不一定经过根节点 ⭐
合法路径示例：
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
路径1: [5] (单个节点) ✓
路径2: [4,5,8] (经过根节点) ✓
路径3: [7,11,4] (不经过根节点) ✓
路径4: [11,4,5,8,13] (经过根节点) ✓
非法路径：
[11,4,11] ✗ (11 出现两次)
[7,11,13] ✗ (11 到 13 没有直接边)
通过以上例子大家应该知道什么是路径了，那咱们下面对路径进行分析
问题分析
核心难点
难点1: 路径不一定经过根节点
解决: 需要遍历每个节点，尝试以它为拐点
难点2: 路径可以拐弯
解决: 对于每个节点，考虑 左子树+节点+右子树
难点3: 节点值可能为负
解决: 如果子树路径和为负，不如不选
难点4: 返回给父节点的值 ≠ 经过当前节点的最大路径
解决: 区分两个概念
- 经过当前节点的最大路径和（可以拐弯）
- 从当前节点出发的最大路径和（不能拐弯）
两个重要概念
概念1: 以 node 为拐点的最大路径和
= node.val + max(0, 左子树贡献) + max(0, 右子树贡献)
说明: 可以同时选择左右子树（形成拐弯路径）
概念2: 从 node 出发向上的最大贡献值
= node.val + max(0, max(左子树贡献, 右子树贡献))
说明: 只能选择左或右其中之一（不能拐弯）
示例:
-10
/ \
9 20
/ \
15 7
节点 20:
- 作为拐点的路径: 15 + 20 + 7 = 42 ✓
- 向上的贡献: 20 + max(15, 7) = 35
(因为不能同时选15和7，否则父节点-10会形成分叉)
解题思路
递归（后序遍历）⭐⭐⭐
核心思想
递归思路:
1. 对于每个节点，计算以它为拐点的最大路径和
2. 更新全局最大值
3. 返回从该节点出发向上的最大贡献值
递归返回值:
从当前节点出发，向父节点延伸的最大路径和
= node.val + max(0, max(leftGain, rightGain))
全局变量:
maxSum: 记录所有节点作为拐点时的最大路径和
图解分析
以 root = [-10,9,20,null,null,15,7] 为例：
树结构:
-10
/ \
9 20
/ \
15 7
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
后序遍历过程:
1. 访问叶子节点 15:
leftGain = 0 (没有左子树)
rightGain = 0 (没有右子树)
以 15 为拐点的路径和:
= 15 + max(0, 0) + max(0, 0) = 15
更新 maxSum = 15
返回给父节点 20 的贡献:
= 15 + max(0, max(0, 0)) = 15(可以理解为层层向上进贡，每个节点，分别可以贡献多少贡献点)
2. 访问叶子节点 7:
以 7 为拐点的路径和 = 7
更新 maxSum = 15 (不变)
返回贡献 = 7
3. 访问节点 20:
leftGain = 15 (来自节点15)
rightGain = 7 (来自节点7)
以 20 为拐点的路径和:
= 20 + max(0, 15) + max(0, 7)
= 20 + 15 + 7 = 42 ⭐
更新 maxSum = 42（因为有两种情况嘛，一种是以该 node 为拐点，另外一种是给父结点贡献）
返回给父节点 -10 的贡献:
= 20 + max(0, max(15, 7))
= 20 + 15 = 35
(只能选左或右，不能同时选)
4. 访问叶子节点 9:
以 9 为拐点的路径和 = 9
返回贡献 = 9
5. 访问根节点 -10:
leftGain = 9 (来自节点9)
rightGain = 35 (来自节点20)
以 -10 为拐点的路径和:
= -10 + max(0, 9) + max(0, 35)
= -10 + 9 + 35 = 34
maxSum = 42 (不变)
返回贡献:
= -10 + max(0, max(9, 35))
= -10 + 35 = 25
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
最终答案: maxSum = 42
最优路径: 15 → 20 → 7
这时候又有同学要问了，为什么要用 max(0,gain)？那我们来深入剖析一下
原因: 节点值可能为负
示例:
5
/ \
-3 2
节点 5:
leftGain = -3
rightGain = 2
如果不用 max(0, gain):
以 5 为拐点 = 5 + (-3) + 2 = 4
用 max(0, gain):
以 5 为拐点 = 5 + max(0, -3) + max(0, 2)
= 5 + 0 + 2 = 7
结论: 如果子树贡献为负，不如不选
代码实现
核心版本
/**
* 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 maxSum;
public:
int maxPathSum(TreeNode* root) {
maxSum = INT_MIN;
maxGain(root);
return maxSum;
}
private:
/**
* 计算从节点出发的最大路径贡献值
* 同时更新全局最大路径和
*/
int maxGain(TreeNode* node) {
if (node == nullptr) {
return 0;
}
// 递归计算左右子树的最大贡献值
// 如果贡献值为负，则不选（用0代替）
int leftGain = max(0, maxGain(node->left));
int rightGain = max(0, maxGain(node->right));
// 以当前节点为拐点的路径和
int pathSum = node->val + leftGain + rightGain;
// 更新全局最大值
maxSum = max(maxSum, pathSum);
// 返回从当前节点出发的最大贡献值
// 只能选择左或右子树其中之一
return node->val + max(leftGain, rightGain);
}
};
时间复杂度: O(n) - 每个节点访问一次
空间复杂度: O(h) - 递归栈深度，h 为树的高度
关键点详解
关键点1: 为什么是后序遍历？
后序遍历顺序: 左 → 右 → 根
原因:
需要先知道左右子树的信息，才能计算当前节点
递归顺序:
1. 先递归左子树，得到 leftGain
2. 再递归右子树，得到 rightGain
3. 最后处理当前节点
如果用前序:
先处理根节点，但不知道左右子树的信息
无法计算以根为拐点的路径和
关键点2: 返回值 vs 更新值
两个不同的值:
值1: 以当前节点为拐点的路径和
= node->val + leftGain + rightGain
用途: 更新全局最大值 maxSum
特点: 可以同时包含左右子树
值2: 从当前节点向上的贡献值
= node->val + max(leftGain, rightGain)
用途: 返回给父节点
特点: 只能包含左或右子树
示例:
5
/ \
4 8
节点 5:
leftGain = 4, rightGain = 8
拐点路径和 = 5 + 4 + 8 = 17 (更新 maxSum)
向上贡献 = 5 + max(4, 8) = 13 (返回给父节点)
这就是刚才提到的两种不同的值
