子问题视角：分治与动态规划
树形 DP
它其实就是后序遍历 + 一点状态
树形 DP 听起来是个新东西，其实代码形状你早就写过： 就是二叉树的递归遍历， 只不过每个节点返回的不再是一个简单的值，而是一组状态。
function dfs(node) {
if (!node) return /* base case */;
const L = dfs(node.left); // ⭐ 先拿到左右子树的答案
const R = dfs(node.right);
return /* 用 L、R 和 node.val 组合出本节点的状态 */;
}⭐ 一定是后序（先递归左右，再处理自己）—— 因为「当前节点的最优解」必须建立在「子树的最优解」之上。 这就是子问题视角在树上的样子。
📌 树形 DP 天然不用管遍历顺序（递归帮你保证了子问题先算）， 省掉了区间 DP里最容易错的那一环。 它的难点在别处。
⭐ 核心难点：返回值 ≠ 答案
这是树形 DP 唯一真正的坎，而且它在最经典的那道题上暴露得最彻底。
二叉树中的最大路径和（力扣 124）：路径可以从任意节点开始、 任意节点结束，但不能重复经过节点。求路径上节点值之和的最大值。
关键在于「路径」在一个节点上有两种形态：
a a
/ \ / \
b c b c
经过 a 拐弯：b-a-c 向上延伸：只能选 b 或 c 中的一支
（可以是答案） （才能接到 a 的父节点上）🚨 拐弯的那条路径不能往上传 —— 它已经用掉了 a 的两个方向， 父节点再接上来就会分叉，不是一条路径了。
⭐ 所以递归函数返回单边最大贡献，而答案在遍历过程中用全局变量更新：
function maxPathSum(root) {
let best = -Infinity;
const gain = (node) => {
if (!node) return 0;
const L = Math.max(0, gain(node.left)); // 🚨 负贡献剪掉，见下文
const R = Math.max(0, gain(node.right));
best = Math.max(best, node.val + L + R); // ⭐ 答案：允许在这里拐弯
return node.val + Math.max(L, R); // ⭐ 返回：只能带一支往上走
};
gain(root);
return best;
}⚠️ 那两行的不对称就是这道题的全部：一个加 L + R，一个加 max(L, R)。
🚨 两种错法，都能通过力扣给的第一个示例
实测三种实现在同一批树上的结果：
用例 正确 ①返回拐弯值 ②不剪负贡献
[1,2,3] 6 6 ✅ 6 ✅
[-10,9,20,null,null,15,7] 42 41 ❌ 42 ✅
[-100,1,2] 2 -97 ❌ 2 ✅
[10,-5,-5] 10 10 ✅ 0 ❌
[2,-1] 2 2 ✅ 1 ❌⚠️ 力扣的两个官方示例是第一、二行。
第一行两种错法都通过；第二行只抓到错法①。
错法②（不剪负贡献）用官方示例根本测不出来 —— 得自己造 [10,-5,-5]。
⭐ 而且这两种错法的暴露条件几乎不重叠。按节点值的符号分布各造 3000 棵随机树：
树里的节点值 错法① 暴露 错法② 暴露
有正有负 55.7% 34.0%
全是正数 61.4% 0.0% ← 完全测不出来
全是负数 67.7% 41.8%🚨 全正数的树上错法②一次都不暴露 —— 没有负贡献，Math.max(0, …) 剪不剪都一样。
而算法题的示例数据十有八九是正数。
📌 判据：凡是靠 Math.max(0, …) 剪枝的地方，自测必须专门放负数进去。
错法①：把拐弯的值当返回值
return node.val + L + R; // ❌这样返回的是「经过本节点拐弯的最大和」，父节点接上去就成了分叉。
症状是 [-100, 1, 2] 返回 -97 而不是 2 ——
它被迫把那个 -100 的根算进去了，因为它从头到尾只报告了根节点的值。
错法②：不剪负贡献
const L = gain(node.left); // ❌ 少了 Math.max(0, ...)子树贡献是负的时候，不接它比接它好。Math.max(0, ...) 表达的就是
「这一支我不要了」。
症状是 [10, -5, -5] 得到 0 而不是 10 ——
两个 -5 硬被加上，把根的 10 抵消掉了。
🚨 ⚠️ 注意 Math.max(0, ...) 只能用在贡献上，不能用在 best 上。
best 的初值必须是 -Infinity，不能是 0 —— 否则全负数的树（如 [-3]）
会返回 0，而正确答案是 -3。路径至少包含一个节点，不能为空。
同一个骨架的三道题
⭐ 认出这个模式之后，一批题就是同一段代码换个组合方式：
| 题 | 返回值（往上传） | 答案（在过程中更新） |
|---|---|---|
| 124 最大路径和 | val + max(L, R) |
val + L + R |
| 543 二叉树的直径 | 1 + max(L, R)（深度） |
L + R（边数） |
| 104 最大深度 | 1 + max(L, R) |
就是返回值本身 |
// 543 直径：和 124 是同一个骨架
function diameterOfBinaryTree(root) {
let best = 0;
const depth = (n) => {
if (!n) return 0;
const L = depth(n.left), R = depth(n.right);
best = Math.max(best, L + R); // ⭐ 答案：左深 + 右深
return 1 + Math.max(L, R); // ⭐ 返回：深度只能算一支
};
depth(root);
return best;
}📌 只有 104 最大深度这种「答案就是返回值」的题，才不需要全局变量。 一旦答案可能出现在某个中间节点而不是根节点，就必须分开。
打家劫舍 III：一个节点带多个状态
力扣 337：树上每个节点有值，相邻的两个节点不能同时选，求最大和。
这里每个节点有两种状态：偷 或 不偷。 所以返回值不是一个数，而是一个二元组：
function rob(root) {
// 返回 [不偷本节点的最大值, 偷本节点的最大值]
const dfs = (n) => {
if (!n) return [0, 0];
const [lNo, lYes] = dfs(n.left);
const [rNo, rYes] = dfs(n.right);
return [
Math.max(lNo, lYes) + Math.max(rNo, rYes), // 不偷：孩子随意
n.val + lNo + rNo, // 🚨 偷：孩子必须不偷
];
};
return Math.max(...dfs(root));
}⭐ 返回二元组，一次遍历搞定。 这是树形 DP 的通用手法： 状态多了就多返回几个分量，而不是多跑几遍。
⚠️ 朴素递归慢在哪：多做了三千倍的函数调用
很多人的第一版是「偷了就跳过孩子、直接从孙子继续」：
// ❌ 没有记忆化：孙子层被重复计算
const rob = (n) => {
if (!n) return 0;
let take = n.val;
if (n.left) take += rob(n.left.left) + rob(n.left.right);
if (n.right) take += rob(n.right.left) + rob(n.right.right);
return Math.max(take, rob(n.left) + rob(n.right));
};它是对的，但每个节点被算了很多遍。实测满二叉树，看调用次数而不是看耗时：
节点数 朴素递归调用次数 二元组调用次数 调用次数之比
16383 14,463,795 32,767 441×
65535 151,466,803 131,071 1,156×
262143 1,586,180,915 524,287 3,025×⭐ 调用次数是纯结构性的（跟节点值无关），所以这三行完全可复现。
二元组版的次数还有个精确公式：节点数 × 2 + 1（每个节点一次，加上所有空指针）。
🚨 26 万个节点，朴素版做了 15.9 亿次函数调用 —— 平均每个节点 6051 次。
这正是动规框架里说的重叠子问题：
rob(孙子) 既被「偷儿子」这条路算，又被「不偷儿子」那条路算。
⚠️ 别去记「快多少倍」这个数。 耗时那一列里，朴素版是稳的 （26 万节点约 5 秒），但二元组版只要两三毫秒 —— 大数除以极小数， 商完全被 JIT 预热主导：
262143 节点 朴素 5081 ms 二元组 3.3 ms（冷启动）→ 1546×
二元组 2.8 ms（预热后）→ 1811×
16383 节点 朴素 44 ms 二元组 1.5 ms（冷启动）→ 29×
二元组 0.2 ms（预热后）→ 230×🚨 同一台机器、同一份代码，16383 那一行的倍数在 29× 和 230× 之间摇摆。 ⭐ 所以这类对比要报调用次数比（441×/1156×/3025×，确定性）， 耗时只用来说明「一个五秒、一个三毫秒」这个量级差别。
📌 两种修法：加一个 Map 备忘录（记忆化搜索），
或者像上面那样改状态定义、返回二元组（等价于自底向上递推）。
⭐ 后者更快也更短 —— 树形 DP 里几乎总是选它。
模板
function treeDP(root) {
let ans = /* 全局答案的初值 */ -Infinity;
const dfs = (node) => {
if (!node) return /* base case：注意是 0 还是 -Infinity 还是 [0,0] */;
const L = dfs(node.left);
const R = dfs(node.right);
ans = /* 用 L、R、node 组合出「以本节点为最高点」的答案，更新全局 */;
return /* 本节点能往上提供的状态 */;
};
dfs(root);
return ans;
}写之前先回答三个问题：
- 每个节点需要几个状态？ 一个 → 返回数值；多个 → 返回数组/对象
- 答案会出现在中间节点吗？ 会 → 需要全局变量；只在根 → 直接返回
- base case 是 0 还是 -Infinity？ 空节点「贡献 0」用 0； 「不存在的方案」用 -Infinity
一般的树（不只是二叉树）
上面都是二叉树。换成多叉树或图上的树， 骨架一样，只是把「左右孩子」换成「遍历邻接表」：
const dfs = (u, parent) => {
let acc = /* 初值 */;
for (const v of graph[u]) {
if (v === parent) continue; // 🚨 无向图存树时，必须排除回到父节点
const sub = dfs(v, u);
acc = /* 累积 */;
}
return acc;
};⚠️ 那个 if (v === parent) continue 是无向图存树时最容易漏的一行 ——
漏了会在父子之间来回递归，直接栈溢出。
下一步
区间 DP 的状态是「一段区间」，树形 DP 的状态是「一个节点」。 还有一类题，状态既不是位置也不是节点，而是你此刻处于哪个身份 —— 持有股票 / 不持有、刚卖出 / 冷冻期。那就是 状态机 DP。
练习
勾选记录做过哪些，0 / 7 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。
- 543. 二叉树的直径简单树形 DP 最短的一道；返回值是深度、答案是左深+右深，先在这题上分清这两者
- 124. 二叉树中的最大路径和困难⭐ 本篇主讲。两个坑：返回值只能带一支往上，以及负贡献要剪成 0
- 337. 打家劫舍 III中等返回二元组 [不偷, 偷] 一次遍历搞定；对照朴素递归感受一下重叠子问题
- 687. 最长同值路径中等和 543 同骨架，只是多一个「值要相等」的条件；边界情况不少
- 1372. 二叉树中的最长交错路径中等每个节点两个状态（从左来 / 从右来），是二元组返回值的又一个例子
- 979. 在二叉树中分配硬币中等⭐ 返回值可以是负数（表示子树缺硬币）；答案累加的是流量的绝对值
- 968. 监控二叉树困难三状态树形 DP（未覆盖/已覆盖/装了摄像头），也是贪心能过但 DP 更稳的题
⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。