11 树形 DP 进阶：二叉树中的最大路径和

树形 DP 进阶：二叉树中的最大路径和

摘要

LeetCode 124 是二叉树专题里最典型的困难题之一。它难的不是代码量，而是状态定义：一条路径既可能只经过单侧子树，也可能在当前节点拐弯，把左右子树同时接起来；但当前节点返回给父节点的值，又绝不能同时带上左右两边。只要没有把“全局最优路径”和“向上可贡献路径”分开，代码就一定会错。本文会用这道题完整讲透树形 DP 的思考方式，并对整个二叉树专栏做一次系统复盘。

---

第 1 章 LeetCode 124：题目为什么难

路径定义是：

• 可以从任意节点出发，到任意节点结束
• 路径上的节点必须连通
• 不能重复经过节点

这意味着答案不一定经过根，也不一定是一条根到叶路径。真正的最优路径，可能在某个中间节点处形成“左子树 → 当前节点 → 右子树”的拐点。

这和前面的 Path Sum 完全不同。Path Sum 是“自顶向下沿一条根到叶路径”，而最大路径和允许在树中间闭合。

---

第 2 章 正确状态：返回什么给父节点

2.1 不能把左右都带上去

假设当前节点是 node。如果父节点要继续把路径向上延伸，那么经过 node 往上走时，只能从左边和右边二选一。

因为一条简单路径在父节点处如果再往上延伸，就不允许在 node 同时保留左右两条分支，否则路径会分叉，不再是一条线。

所以递归函数返回给父节点的，应该是：

node 对父节点的最大单侧贡献值

公式是：

$$gain(node)=node.val+\max (0,gain(left),gain(right))$$

之所以和 0 比较，是因为负贡献不如不要。

2.2 当前节点处的全局候选值

虽然返回给父节点时只能选一边，但在当前节点自己这里，可以把左右都接上，形成一条完整路径：

$$price(node)=node.val+\max (0,gain(left))+\max (0,gain(right))$$

这个值不能返回给父节点，但可以用来更新全局答案。

---

第 3 章 代码实现

private int maxSum = Integer.MIN_VALUE;
 
public int maxPathSum(TreeNode root) {
    maxGain(root);
    return maxSum;
}
 
private int maxGain(TreeNode node) {
    if (node == null) {
        return 0;
    }
 
    int leftGain = Math.max(0, maxGain(node.left));
    int rightGain = Math.max(0, maxGain(node.right));
 
    int currentPathSum = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, currentPathSum);
 
    return node.val + Math.max(leftGain, rightGain);
}

这个写法浓缩了树形 DP 的核心：

• 递归返回值服务于父节点
• 全局变量记录整棵树的最佳答案
• 两者含义不同，不能混用

---

第 4 章 为什么一定是后序遍历

因为当前节点需要先知道左右子树各自能提供多大贡献，才能决定：

1. 当前节点作为拐点时的路径和
2. 返回给父节点时该带哪一边

这就是最标准的“先拿子问题结果，再汇总”的后序模型。

4.1 与平衡二叉树的类比

在 平衡二叉树 里，后序返回的是高度；在这道题里，后序返回的是单侧最大贡献值。模型完全一致，只是状态含义变了。

---

第 5 章 二叉树专栏总复盘

5.1 题目索引

篇数	主题	覆盖题目	关键能力
01	DFS 遍历	144, 94, 145	前中后序与显式栈
02	BFS 遍历	102, 107, 103	按层切边界
03	结构判定	100, 101, 110	递归语义与后序高度
04	指针操作	114, 116, 117	原地重连与层连接
05	树的重建	105, 106	区间切分与根定位
06	BST 判定修复	98, 99	中序递增性质
07	BST 计数生成	96, 95	Catalan 数与分治枚举
08	有序序列转 BST	108, 109	分治平衡与链表中序模拟
09	深度问题	111, 104	定义边界与 BFS/DFS 选择
10	根到叶路径	112, 113, 129	路径状态与回溯
11	树形 DP	124	返回值与全局值分离

5.2 这一整套专栏的主线是什么

如果把 11 篇文章压缩成三条真正值得记住的主线，它们分别是：

1. 遍历主线：前序、中序、后序、层序分别对应不同处理时机
2. 返回值主线：函数究竟给父节点返回什么，是树题成败关键
3. 结构约束主线：普通树、二叉搜索树、完美二叉树，约束不同，解法就会降维或变形

5.3 高频考点建议

如果你是面试准备阶段，建议至少把以下题做到闭卷写出：

1. 144/94/145：递归和至少一种迭代
2. 102：标准层序遍历
3. 110：后序返回高度
4. 105：前序 + 中序重建
5. 98：上下界验证 BST
6. 124：区分全局答案与向上贡献

这六道题覆盖了二叉树最核心的思维骨架。

5.4 下一步怎么学

完成二叉树专题后，顺着这条链路继续学习最自然：

1. 进入 图：把树上的 DFS/BFS 推广到一般图结构
2. 进入 递归与回溯：把路径状态设计推广到组合搜索问题
3. 进入 动态规划：把树形 DP 的状态抽象迁移到线性 DP 和区间 DP

二叉树不是终点，而是算法抽象训练场

真正难的不是节点和指针，而是：你能不能把问题拆成子问题，并为递归函数设计出稳定的输入输出语义。二叉树之所以重要，正因为它把这种能力训练得最完整。

---

专栏后记

到这里，二叉树专栏已经具备完整的学习闭环：从遍历入门，到结构判定、构造、BST、路径，再到树形 DP 收尾。相比线性表和栈队列，二叉树更像一道分水岭。过了这一关，后面的图、回溯、DP 都会变得更自然，因为你已经习惯了两件最重要的事：

• 先定义递归语义，再写代码
• 先区分局部状态和全局答案，再决定返回值

这两件事，正是整个算法训练的主轴。