树形 DP：从节点状态到子树合并
通过树上打家劫舍、树的直径和节点状态合并，理解树形 DP 为什么通常使用后序遍历。
知识目录数据结构与算法：从基础到工程实践33 / 77
以前看到“树形 DP：从节点状态到子树合并”，我会下意识去找一份模板保存下来。后来发现这样学得很快，忘得也快，因为我能理解普通 DP 的前后位置关系，但状态搬到树上以后，没有固定的前一项，最开始完全不知道该从哪里转移。所以这篇不从标准答案起步，而是顺着我当时的疑问一点点往下拆。
树形 DP 是动态规划在树结构上的应用。它的核心是：每个节点的答案由子节点答案合并而来。只要树没有环，父子依赖就天然适合递归。
树形 DP 的思路
图：先算子树状态，再合并成当前节点状态
树形 DP 的常见问题：
- 树的直径。
- 二叉树最大路径和。
- 树上打家劫舍。
- 以某个节点为根的子树大小。
- 树形背包。
树上打家劫舍
每个节点有两个状态：
dp[0]：不偷当前节点的最大收益。dp[1]：偷当前节点的最大收益。
int rob(TreeNode root) {
int[] ans = dfs(root);
return Math.max(ans[0], ans[1]);
}
int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
int rob = node.val + left[0] + right[0];
return new int[]{notRob, rob};
}
偷当前节点时，孩子不能偷；不偷当前节点时，孩子可偷可不偷。
树的直径
树的直径是任意两个节点之间最长路径。对每个节点来说，穿过它的最长路径等于左子树高度 + 右子树高度。
int diameter = 0;
int diameterOfBinaryTree(TreeNode root) {
height(root);
return diameter;
}
int height(TreeNode node) {
if (node == null) return 0;
int left = height(node.left);
int right = height(node.right);
diameter = Math.max(diameter, left + right);
return Math.max(left, right) + 1;
}
这里返回给父节点的是高度，但在递归过程中顺便更新全局直径。
树形 DP 的常见状态
| 状态 | 含义 |
|---|---|
size[u] |
以 u 为根的子树大小 |
height[u] |
以 u 为根的高度 |
dp[u][0/1] |
当前节点选或不选 |
dp[u][k] |
当前子树选择 k 个元素的最优值 |
我的分析
树形 DP 比普通 DP 更容易想，因为遍历顺序通常就是后序遍历：先处理孩子，再处理父亲。难点在于状态要不要区分“当前节点选不选”“路径是否向父节点延伸”。
如果某个状态需要同时使用父亲和孩子的信息，可能要考虑换根 DP，但普通学习阶段先掌握自底向上的树形 DP 就够了。
面试题
- 树形 DP 为什么通常使用后序遍历？
- 树上打家劫舍为什么需要两个状态？
- 树的直径中，返回值和全局答案为什么不是同一个含义？
- 什么情况下要考虑换根 DP？
- 树形 DP 和普通递归有什么区别？
JARVIS · 当前文章
有哪里没看懂？可以只问这篇。
Jarvis 会限定在《树形 DP：从节点状态到子树合并》及其公开关联内容中检索，并把引用定位回原文章节。