tree DP · 后序聚合

树形 DP · 后序聚合与拐弯路径

树上的问题几乎都有一个共同结构——一个节点的答案，要先知道它孩子的答案。所以天然用一次后序遍历解决：先把左右子树彻底算完、拿到它们交上来的结果，再合成自己的、交给父亲。本页从最朴素的求树高起步，延伸到《编程之美》那道经典的二叉树最大距离（直径），再到带权的最大路径和，最后引出另一种范式树上打家劫舍。每节都可单步观察递归如何下潜、数字如何逐层向上返回、全局最优在哪个节点被刷新、代码逐行点亮。四节递进：后序聚合 → 二叉树直径 → 最大路径和 → 树上打家劫舍。

1 · 后序聚合：每个节点向上只交一个数

foundation · 后序聚合

树形问题大多具有同一结构：一个节点的答案，要先知道它孩子的答案。因此天然适合后序处理——先把左右子树完整算完，取得它们返回的结果，再合成自己的、交给父亲。本节用最朴素的例子引入：求树高。height(node) 约定：空树 = 0，否则 = 1 + max(左子树高, 右子树高)。每个节点只向上返回一个数——这一点是后面三节的共同基础。

观察「调用→返回」的轨迹。 点「下一步」按真实递归顺序执行：进入一个节点 → 持续下潜到最深的叶子 → 叶子先返回 → 逐层将数字向上返回（节点右上角的金色药丸 = 它返回的高度）。绿色实心 = 此刻正在计算的节点；浅绿 = 已返回。

1.1 · 这套结构在后续各节持续复用

概括上面的函数：递归左右孩子 → 用孩子的结果合成一个值 → 返回。这就是树形 DP 的基本结构。接下来三节只改动「合成与返回这两步具体计算什么」：

二叉树直径：仍返回「树高」，但经过每个节点时同时用「左高 + 右高」更新一个全局最长路径——拐点不一定在根。
最大路径和：节点带权、可为负，返回「向下最大增益」，负值就剪去不带。
树上打家劫舍：向上返回的不再是一个数，而是一对状态「抢 / 不抢」——树形 DP 的另一种形态。

2 · 二叉树直径：最长的那条路径，在某个节点「拐弯」

core · 二叉树直径

直径 = 树里任意两节点间最长路径的边数。直接求解并不容易——两个端点从何确定？换个视角：这条最长路径一定在某个节点处「拐弯」（从它的左子树最深处下来，经过它，再下到右子树最深处）。因此只需枚举「拐点」：在每个节点 x 计算「左子树往下最长链 + 右子树往下最长链」，取全局最大即可。而「往下最长链」正是后序聚合里的树高。于是一次后序遍历：返回树高，同时用左高 + 右高更新全局 best。这就是那篇《编程之美》题解讲的「求二叉树中节点的最大距离」。

本例特意把拐点放在非根节点。 单步执行可以看到全局 best 在节点 b 处被刷新为 6（路径 h-f-d-b-e-g-i），根 a 反而不在最长路径上——直径不一定经过根，这是最常见的直觉误区。

2.1 · 两个数字需要区分：返回的是「链」，更新的是「路径」

每个节点身上有两个量。返回值 1+max(L,R)：只能向上带一条链（父亲将来还要继续往上走，路径不能在此分叉）。更新量 L+R：在本节点拐弯的完整路径，它不向上返回、只用于和全局 best 比较。「向上返回一个、同时更新一个全局」——这正是树形 DP 里聚合型问题的通用范式，最大路径和与此完全一致。

复杂度。 每个节点只被 depth 访问一次， $O(n)$ 。对比朴素做法「对每个节点都 DFS 求一遍两侧最深」是 $O(n^2)$ ——后序聚合的高效之处，在于孩子的结果只计算一次、被父亲直接复用。

3 · 最大路径和：节点带权、可为负，负值则剪去

extend · 最大路径和

给节点加上权值（可正可负），求任意一条路径上节点值之和的最大值 (LeetCode 124)。框架与直径完全相同：在每个节点拐弯，best = node.val + L + R；向上只能带一条链。唯一的新增是负数：某条向下的链如果增益为负，带上它只会拉低总和——所以 L = max(gain(node.left), 0)，负值直接按 0 处理（等于「不取这条链」）。

本例 = LeetCode 124 经典样例。 根 A 的值是 -10，关键正在于此：最优路径不经过根，而是在 C(20) 拐弯， ${15 \to 20 \to 7 = 42}$ 。单步观察 -10 那一侧的增益如何被剪、best 如何落在 C。

3.1 · 与直径同属一个框架

问题	向上返回（一条链）	路过时更新的全局（拐弯）
直径	1 + max(L, R)	L + R （边数）
最大路径和	val + max(L, R)	val + L + R

都是「聚合型」树形 DP：节点向上返回一个标量，经过时用「左 + 自己 + 右」更新一个全局最优。差别只在是否带权、是否需要 $\max (\cdot , 0)$ 剪去负值。

树上打家劫舍转向另一类问题：节点向上返回的不是一个数，而是一对互斥状态。

4 · 树上打家劫舍：向上返回的是「一对状态」，不是一个数

paradigm · 状态型

每个节点有钱 val，规则：相邻（父子）不能同时抢，求最多能抢多少 (LeetCode 337)。前三节节点向上只返回一个数；这里不再适用——父亲是否抢，取决于孩子是否抢。于是每个节点向上返回一对状态 [抢, 不抢]:

抢 node = val + 左.不抢 + 右.不抢（孩子不能抢）。

不抢 node = max(left) + max(right)（孩子抢与不抢均可，各取较大）。

最终答案 = max(根.抢, 根.不抢)。这就是状态型树形 DP：一个节点带多个互斥状态，向上返回的是一整组，父亲再按规则组合。

4.1 · 两种树形 DP 范式小结

范式	节点向上返回什么	本页例子
聚合型	一个标量（一条链的值），经过时更新全局最优	树高 · 直径 · 最大路径和
状态型	一组互斥状态（如 [选，不选]），父亲按约束组合	打家劫舍

两者共用同一套后序聚合结构，区别只在「向上返回的内容」是标量还是状态向量。判明问题属于哪一型后，代码结构基本一致。

5 · 一张表概览四节

同一套后序聚合结构，变的只是「节点向上返回什么」「经过时如何更新全局」：

节	问题	向上返回（一条链）	路过时更新的全局
后序聚合	树高	1 + max(L, R)	—
直径	直径	1 + max(L, R)	best = max(best, L + R)
最大路径和	最大路径和	val + max(L, R)	best = max(best, val + L + R)
打家劫舍	打家劫舍	[val + L₋ + R₋, max(L) + max(R)]	根处 max（抢，不抢）

前三行是「聚合型」（向上返回一个标量）；第四行是「状态型」（向上返回一组互斥状态）。判明属于哪一型后，代码结构基本一致。

它的实际工程应用。 编译器在 AST（语法树）上做常量折叠 / 类型推导 / 寄存器需求估算、文件系统计算目录占用、组织架构计算最长汇报链、最小支配集 / 最小点覆盖、以及大量「子树答案可合成父答案」的统计——只要数据是树、且整体最优可由局部组合得出，大多属于这一类。

与其他系列的关联： 这里的后序遍历结构与搜索里的 DFS 是同一种递归，区别在于树形 DP 在回溯（归途）阶段聚合答案；而「按决策逐层转移状态」的思路，与背包九讲相通——只是把线性 DP 表换成了树。