tree DP · 后序聚合

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

树上的问题几乎都有一个共同结构：一个节点的答案，要先知道它孩子的答案。所以天然用一次后序遍历解决——先把左右子树彻底算完、拿到它们交上来的结果，再合成自己的、交给父亲。本页从最朴素的求树高起步，延伸到《编程之美》那道经典的二叉树最大距离，再到带权的最大路径和，最后引出另一种范式：树上打家劫舍。四节依次是后序聚合、二叉树直径、最大路径和、树上打家劫舍。

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

foundation · 后序聚合

本节用最朴素的例子引入：求树高。height(node) 约定空树为 $0$ ，否则为 $1 + \max(\text{左子树高}, \text{右子树高})$ 。每个节点只向上返回一个数——这一点是后面三节的共同基础。

图 1-1 · 按真实递归顺序单步执行：进入一个节点、持续下潜到最深的叶子、叶子先返回、逐层把数字向上交。节点右上角的金色药丸是它返回的高度，绿色实心是此刻正在计算的节点，浅绿是已返回。

1.1 · 复用同一套结构

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

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

2 · 二叉树直径与拐点

core · 二叉树直径

直径 (diameter) 是树里任意两节点间最长路径的边数。直接求解并不容易——两个端点从何确定？换个视角：这条最长路径一定在某个节点处「拐弯」，从它的左子树最深处下来，经过它，再下到右子树最深处。因此只需枚举拐点：在每个节点 $x$ 计算「左子树往下最长链加右子树往下最长链」，取全局最大。而往下最长链正是后序聚合里的树高。于是一次后序遍历：返回树高，同时用左高加右高更新全局最优。

图 2-1 · 拐点被特意安排在非根节点。可单步观察全局最优在节点 b 处被刷新为 6（路径 h-f-d-b-e-g-i 共 7 个节点、6 条边），根 a 反而不在最长路径上。

2.1 · 链与路径的区分

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

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

3 · 带权的最大路径和

extend · 最大路径和

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

图 3-1 · LeetCode 124 的经典样例：根 A 的值是 −10，最优路径不经过根，而是在 C (20) 拐弯，

15 \to 20 \to 7 = 42

。可单步观察 −10 那一侧的增益如何被剪。

3.1 · 与直径同属一个框架

表 3-1 · 两个问题只差是否带权、是否需要剪去负值。
问题	向上返回（一条链）	路过时更新的全局（拐弯）
直径	1 + max(L, R)	L + R（边数）
最大路径和	val + max(L, R)	val + L + R

都是聚合型树形 DP：节点向上返回一个标量，经过时用「左加自己加右」更新一个全局最优。树上打家劫舍转向另一类问题：节点向上返回的不是一个数，而是一对互斥状态。

4 · 树上打家劫舍与状态型返回

paradigm · 状态型

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

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

不抢 node $= \max(\text{左})+\max(\text{右})$ （孩子抢与不抢均可，各取较大）

最终答案 $= \max(\text{根.抢}, \text{根.不抢})$

这就是状态型树形 DP：一个节点带多个互斥状态，向上返回的是一整组，父亲再按规则组合。

图 4-1 · LeetCode 337 的经典样例，答案 7 由根加两个孙节点凑出。可单步观察每个节点向上交出的那对数字如何被父亲组合。

4.1 · 两种范式小结

表 4-1 · 两种范式共用后序聚合结构，区别只在向上返回的内容。
范式	节点向上返回什么	本页例子
聚合型	一个标量（一条链的值），经过时更新全局最优	树高、直径、最大路径和
状态型	一组互斥状态（如「选 / 不选」），父亲按约束组合	打家劫舍

5 · 四节概览

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

表 5-1 · 四节的返回值与全局更新式对照。前三行是聚合型，第四行是状态型。
节	问题	向上返回（一条链）	路过时更新的全局
后序聚合	树高	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 表换成了树。