02.7.2.2 树形 DP
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.2 区间树形与状态压缩 DP
02.7.2.2-001 树形 DP 是什么?
一句话结论
树形 DP 以节点为状态挂载点,后序递归求解子树,把子树信息合并到当前节点;状态通常随节点返回,父层只依赖子层结果;本质是在树上做自底向上的 DP。
概念解释
- 状态挂节点。
- 后序:先子后父。
原理流程
- 递归左右/子节点。
- 合并子树结果。
- 本层状态返回父层。
代码 / 示例
Info dfs(TreeNode r) {
if (r == null) return base;
Info l = dfs(r.left), rr = dfs(r.right);
return merge(l, rr, r);
}
常见误区
- 误区:先处理当前节点再递归;正解:树形 DP 需子树结果,后序。
- 误区:用全局表存节点状态;正解:随递归返回更直接。
追问
- Q:树形 DP 遍历顺序? A:后序(左右根)。
- Q:复杂度? A:O(n),每节点一次。
02.7.2.2-002 状态怎么挂在节点上?
一句话结论
每个节点返回该子树所需的全部信息(高度、选/不选最优、直径等);多个信息封装成对象或用多个返回值;父层读取子节点状态合并,不再重复遍历子树。
概念解释
- 节点状态:子树聚合信息。
- 封装:多值对象。
原理流程
- 列清父层需要子树提供什么。
- 定义返回结构。
- 子层算好上交。
代码 / 示例
static class Info { int h; int best; }
常见误区
- 误区:只返回一个值导致父层信息不足;正解:按需要封装多值。
- 误区:父层再遍历子树;正解:子树结果已在返回值中。
追问
- Q:什么时候用成员变量? A:全局最优可在递归中更新,局部信息仍返回。
- Q:多叉树怎么聚合? A:遍历所有子节点合并。
02.7.2.2-003 二叉树最大路径和(LC 124)怎么做?
一句话结论
dfs 返回从当前节点向下的最大单边贡献;全局记录“经过当前节点的路径和 = 左贡献 + 右贡献 + 节点值”;单边贡献取 节点值 + max(左,右,0);时间 O(n),空间 O(h)。
概念解释
- 单边贡献:向上回传。
- 经过路径:左右都接。
原理流程
- 递归求左右单边贡献。
- 更新全局最大路径和。
- 返回本节点单边贡献。
代码 / 示例
int dfs(TreeNode r) {
if (r == null) return 0;
int l = Math.max(0, dfs(r.left));
int rr = Math.max(0, dfs(r.right));
ans = Math.max(ans, l + rr + r.val);
return r.val + Math.max(l, rr);
}
常见误区
- 误区:返回左右都接的路径和;正解:向上只能走单边。
- 误区:负贡献也接上;正解:负贡献取 0 舍弃。
追问
- Q:全负节点答案? A:最大单节点值。
- Q:复杂度? A:O(n) 时间 O(h) 栈。
02.7.2.2-004 打家劫舍 III(LC 337)两状态怎么转移?
一句话结论
每节点返回偷/不偷两个值:偷则子节点必须不偷;不偷则子节点各取偷/不偷最大;rob=left.notRob+right.notRob+val,notRob=max(left)+max(right);时间 O(n)。
概念解释
- 选/不选状态。
- 父子互斥。
原理流程
- 递归左右得两状态。
- 本层偷与不偷分别计算。
- 返回两值。
代码 / 示例
int[] dfs(TreeNode r) {
if (r == null) return new int[]{0, 0};
int[] l = dfs(r.left), rr = dfs(r.right);
int rob = l[1] + rr[1] + r.val;
int notRob = Math.max(l[0], l[1]) + Math.max(rr[0], rr[1]);
return new int[]{rob, notRob};
}
常见误区
- 误区:偷当前还能偷子节点;正解:父子互斥。
- 误区:只返回最大值;正解:父层需要区分选否。
追问
- Q:复杂度? A:O(n)。
- Q:树形与线性打家劫舍区别? A:约束在父子边,后序合并。
02.7.2.2-005 二叉树直径(LC 543)和树形 DP 什么关系?
一句话结论
直径是过某节点的最长左右路径之和;递归返回节点高度,全局更新 左高+右高;高度即单边状态,直径在合并层统计;与最大路径和同框架。
概念解释
- 高度:单边最长边数。
- 直径:跨节点两单边之和。
原理流程
- 递归求左右高度。
- 更新全局直径。
- 返回本节点高度。
代码 / 示例
int dfs(TreeNode r) {
if (r == null) return 0;
int l = dfs(r.left), rr = dfs(r.right);
ans = Math.max(ans, l + rr);
return Math.max(l, rr) + 1;
}
常见误区
- 误区:直径返回值当答案;正解:答案在全局,返回的是高度。
- 误区:高度含当前节点计数口径混乱;正解:统一按边数或节点数。
追问
- Q:复杂度? A:O(n)。
- Q:直径一定过根吗? A:不一定,在任意节点合并。
02.7.2.2-006 树的最长路径/直径(普通树)怎么求?
一句话结论
多叉树同样后序:维护子树最长向下路径,全局记录最长两条向下路径之和;与二叉树直径一致,只是子节点遍历全部孩子;时间 O(n)。
概念解释
- 多叉:多个孩子。
- 最长两条:拼经过本节点路径。
原理流程
- 递归各孩子得向下长度。
- 取最大两条求和更新全局。
- 返回最长一条 + 边。
代码 / 示例
遍历孩子,记录 top1/top2 向下长度;ans=max(ans, top1+top2)
常见误区
- 误区:只取一个孩子路径;正解:直径可跨两个孩子分支。
- 误区:多叉漏遍历孩子;正解:邻接表全遍历。
追问
- Q:带权树直径? A:路径长按边权累加。
- Q:复杂度? A:O(n)。
02.7.2.2-007 树独立集(节点选择不相邻)怎么 DP?
一句话结论
每节点选/不选两状态:选则孩子都不选;不选则孩子各取最优;与打家劫舍 III 同构;求最大权独立集;时间 O(n)。
概念解释
- 独立集:相邻不同选。
- 两状态转移。
原理流程
- 递归孩子状态。
- 选:孩子全不选。
- 不选:孩子取最优。
代码 / 示例
选 = 权值 + Σ孩子.not
不选 = Σmax(孩子.选, 孩子.不选)
常见误区
- 误区:选节点还能选相邻孩子;正解:独立集互斥。
- 误区:无权值默认 1;正解:按题意权值。
追问
- Q:最大独立集与最小点覆盖关系? A:二分图中互补,一般树 DP 求解。
- Q:复杂度? A:O(n)。
02.7.2.2-008 树的最小点覆盖/边覆盖怎么求?
一句话结论
最小点覆盖:每节点选/不选,叶子不选则父必须选;选=1+Σ孩子.not,不选=Σ孩子.选,取根两状态最小;边覆盖按题意匹配边集合,树形/贪心处理。
概念解释
- 点覆盖:每条边至少一端被选。
- 转移:父子选择约束。
原理流程
- 两状态后序。
- 不选当前则孩子必选。
- 根取最小。
代码 / 示例
选 = 1 + Σ孩子.not
不选 = Σ孩子.选
常见误区
- 误区:点覆盖与独立集混淆;正解:约束方向相反,互补关系。
- 误区:叶子不选无约束;正解:叶子不选则其父承担覆盖。
追问
- Q:树是二分图吗? A:是,可用二分图匹配求覆盖。
- Q:复杂度? A:O(n)。
02.7.2.2-009 多子树怎么转二叉树 DP?
一句话结论
多叉树递归遍历所有孩子聚合状态:把孩子状态累加到当前节点的选/不选或最值中;二叉树的左右两支换成孩子列表循环;信息合并方式不变。
概念解释
- 孩子列表:邻接表。
- 循环聚合:替代左右分支。
原理流程
- 遍历所有孩子递归。
- 累加/比较孩子状态。
- 生成本节点状态。
代码 / 示例
for (TreeNode c : children) {
Info ci = dfs(c);
// 聚合到本节点
}
常见误区
- 误区:只处理前两个孩子;正解:遍历全部子节点。
- 误区:邻接表忘排除父节点;正解:有根树递归跳过 parent。
追问
- Q:无根树怎么定根? A:任选节点 DFS,记录父节点防回跳。
- Q:多叉状态聚合? A:按题意累加或取最值。
02.7.2.2-010 树形 DP 递归返回值怎么设计?
一句话结论
返回父层所需的最小信息集:需要区分选择就返回选/不选两值,需要高度就返回高度;全局最优可单独用成员变量更新;避免返回冗余信息导致合并复杂。
概念解释
- 最小信息集。
- 全局答案旁路更新。
原理流程
- 明确父层依赖。
- 设计返回结构。
- 全局最值旁路记录。
代码 / 示例
// 返回 {选, 不选};ans 在递归中更新
常见误区
- 误区:返回整棵子树所有信息;正解:只回传父层需要的。
- 误区:全局变量多线程共享;正解:单次求解局部使用。
追问
- Q:返回数组还是对象? A:两值可用数组,语义清晰用对象。
- Q:答案在根状态还是全局? A:按定义,前缀/根状态或旁路最大。
02.7.2.2-011 选/不选两状态为什么是树形 DP 常见模式?
一句话结论
树边约束常表现为父子互斥(偷不相邻、独立集、点覆盖),天然拆成选当前与不选当前两状态;两状态覆盖所有决策,父层据此合并,是最经典的树形 DP 结构。
概念解释
- 互斥约束。
- 二元状态。
原理流程
- 列父子约束。
- 定义选/不选。
- 转移互斥关系。
代码 / 示例
选:孩子不选;不选:孩子任选最优
常见误区
- 误区:把两状态合并成一个最优值;正解:父层需要知道是否选了当前。
- 误区:状态扩展遗漏;正解:约束多于二元时增加状态类。
追问
- Q:哪些题是两状态? A:打家劫舍 III、独立集、点覆盖。
- Q:三状态树形 DP 有吗? A:有,如带颜色/类型约束。
02.7.2.2-012 子树信息怎么自底向上合并?
一句话结论
递归先得到所有子树状态,再在当前节点按规则合并:累加求和、取最值、组合两状态;合并只使用子节点返回值,不再下钻;父节点随后把合并结果上交。
概念解释
- 自底向上:子先父后。
- 合并规则:按题意。
原理流程
- 子树递归完成。
- 聚合孩子结果。
- 生成本层状态。
代码 / 示例
sum = Σ孩子.sum;best = max(孩子.best)
常见误区
- 误区:合并时重新遍历子树;正解:读返回值即可。
- 误区:合并顺序影响结果;正解:可交换操作顺序无关。
追问
- Q:合并需要父节点信息吗? A:多数只靠子树与本节点值。
- Q:合并代价放哪? A:本层计算计入当前状态。
02.7.2.2-013 树形 DP 空节点怎么初始化?
一句话结论
空子树返回基准状态:高度 0、选/不选均 0、不可达按题意;空节点基准使叶子节点转移可直接套用统一公式,避免叶子特判。
概念解释
- 空基准:叶子的子树。
- 统一公式。
原理流程
- 定义空节点返回值。
- 叶子由空基准合并。
- 公式对所有节点一致。
代码 / 示例
if (r == null) return new Info(0, 0);
常见误区
- 误区:叶子单独写一套转移;正解:空基准统一公式。
- 误区:空节点返回非法状态;正解:按状态定义给基准。
追问
- Q:高度空节点返回几? A:按边数口径返回 0。
- Q:不可达状态怎么给? A:-INF/false。
02.7.2.2-014 树形 DP 复杂度 O(n) 怎么理解?
一句话结论
每个节点递归访问一次,单节点合并孩子为常数(二叉)或 O(孩子数),总边数 n-1,时间 O(n);递归栈 O(h),h 为树高,链形最坏 O(n)。
概念解释
- 节点一次。
- 边遍历一次。
原理流程
- 每节点一次递归。
- 孩子聚合遍历边。
- 栈深为树高。
代码 / 示例
n 节点,n-1 边 → O(n)
常见误区
- 误区:树形 DP 有 O(n²) 子树遍历;正解:状态已随返回值聚合,不重复下钻。
- 误区:空间按 O(n) 堆;正解:递归栈 O(h)。
追问
- Q:深树递归会溢出吗? A:链形 O(n),必要时迭代。
- Q:记忆化在树上需要吗? A:每节点一次,无需 memo。
02.7.2.2-015 树上背包(选课类)怎么做?
一句话结论
节点有体积/价值,选父才能选子,子树内分配容量;dp[u][k] 子树 u 选 k 个/容量 k 的最优;后序把孩子背包合并到父节点,类似树上分组背包;时间 O(n·W) 量级。
概念解释
- 依赖:父子选择关联。
- 树上分组背包。
原理流程
- 后序递归孩子。
- 孩子背包并入父节点 DP。
- 当前节点选/不选更新。
代码 / 示例
dp[u] 初值含 u;合并孩子:dp[u][j] = max(dp[u][j], dp[u][j-t]+dp[v][t])
常见误区
- 误区:孩子背包独立计算不合并;正解:父子在同一容量下分配。
- 误区:合并顺序覆盖;正解:逆序或临时表防止重复取孩子。
追问
- Q:复杂度? A:O(n·W) 到 O(n·W²) 视合并方式。
- Q:选父前提怎么体现? A:不选父则子树不可选。
02.7.2.2-016 树形 DP 与后序遍历什么关系?
一句话结论
树形 DP 计算顺序即后序:先子后父;递归写法天然后序;迭代实现需显式栈记录“子节点已处理”状态位,与后序迭代一致。
概念解释
- 后序:子→父。
- 状态位:子完成后合并。
原理流程
- 递归压入子节点。
- 子层返回后合并。
- 父层上交。
代码 / 示例
dfs(left); dfs(right); merge(root)
常见误区
- 误区:前序就算父层状态;正解:缺子树结果。
- 误区:迭代忘状态位;正解:标记子节点已返回。
追问
- Q:树形 DP 能用前序吗? A:依赖子结果的必须后序。
- Q:层序能做吗? A:自底向上层序也可,但递归后序最自然。
02.7.2.2-017 状态回传与全局最优怎么配合?
一句话结论
需要上交父层的信息走返回值;不向上传递的全局最值(直径、最大路径和)在递归中用成员变量更新;两者分工:返回值服务父层,全局变量记录跨子树答案。
概念解释
- 回传:父层依赖。
- 全局:跨节点最优。
原理流程
- 区分哪些信息上交。
- 返回值封装上交项。
- 全局变量旁路更新答案。
代码 / 示例
int ans;
Info dfs(TreeNode r) { ...; ans = max(ans, 跨节点值); return info; }
常见误区
- 误区:全局最优也塞进返回值;正解:父层用不到的放全局。
- 误区:多棵树复用全局未清零;正解:每棵树前重置。
追问
- Q:不用全局变量可以吗? A:可返回含全局最优的结构,但较繁琐。
- Q:全局变量线程安全? A:单次求解无并发即可。
02.7.2.2-018 多叉树状态聚合有哪些方式?
一句话结论
按题意:求和类累加孩子状态,最值类遍历取最大,组合类(选/不选)分别聚合;遍历所有孩子后生成本节点状态;邻接表递归需排除父节点。
概念解释
- 聚合:加/取/组合。
- 防回跳:记录 parent。
原理流程
- 遍历孩子。
- 按规则聚合。
- 生成本层状态。
代码 / 示例
for (int v : adj[u]) if (v != parent) { Info ci = dfs(v, u); ... }
常见误区
- 误区:无根树不记 parent 回跳;正解:邻接表双向需排除父。
- 误区:聚合漏孩子;正解:遍历完整邻接表。
追问
- Q:多叉树选两条最长路径? A:遍历维护 top1/top2。
- Q:聚合顺序敏感吗? A:可交换规则不敏感。
02.7.2.2-019 树形 DP 常见误区有哪些?
一句话结论
高频错误:前序处理父节点、返回值信息不足、选/不选状态混淆、空节点基准缺失、多叉漏孩子、全局最优与回传混用;按后序、返回结构、空基准、孩子遍历逐项核对。
概念解释
- 顺序:后序。
- 状态:返回完整。
原理流程
- 核对遍历顺序。
- 检查返回信息。
- 补空基准与孩子遍历。
代码 / 示例
排查:后序 / 返回结构 / 选不选 / 空基准 / 多叉遍历 / 全局回传
常见误区
- 误区:二叉树思路套多叉只取两支;正解:遍历全部孩子。
- 误区:递归深度大未评估;正解:链形 O(n) 注意栈深。
追问
- Q:结果缺子树贡献先查什么? A:孩子是否递归到、返回值是否被使用。
- Q:父子约束违反先查什么? A:选/不选转移关系。
02.7.2.2-020 树形 DP 怎么判断该不该用?
一句话结论
问题在树上按父子约束分解、子树独立、答案自底向上合并时用树形 DP;约束是相邻互斥、子树选优、路径跨节点等典型场景;若结构不是树则归其他专题。
概念解释
- 树上子问题。
- 自底向上合并。
原理流程
- 确认结构是树。
- 看子问题是否为子树。
- 选后序状态合并。
代码 / 图示
父子约束 / 子树最优 / 跨节点路径 → 树形 DP
常见误区
- 误区:把线性序列当树做;正解:无层级结构用线性 DP。
- 误区:图有环仍按树形;正解:有环需先判环或换图算法。
追问
- Q:二叉树路径题都归树形 DP 吗? A:求子树聚合的是,单纯遍历不是。
- Q:树形 DP 一般状态数? A:O(n) 节点,单节点常数状态。