罗罗编程学习记录
本页内容 展开查看

02.7.2.2 树形 DP

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.2 区间树形与状态压缩 DP

02.7.2.2-001 树形 DP 是什么?

一句话结论

树形 DP 以节点为状态挂载点,后序递归求解子树,把子树信息合并到当前节点;状态通常随节点返回,父层只依赖子层结果;本质是在树上做自底向上的 DP。

概念解释

  • 状态挂节点。
  • 后序:先子后父。

原理流程

  1. 递归左右/子节点。
  2. 合并子树结果。
  3. 本层状态返回父层。

代码 / 示例

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 状态怎么挂在节点上?

一句话结论

每个节点返回该子树所需的全部信息(高度、选/不选最优、直径等);多个信息封装成对象或用多个返回值;父层读取子节点状态合并,不再重复遍历子树。

概念解释

  • 节点状态:子树聚合信息。
  • 封装:多值对象。

原理流程

  1. 列清父层需要子树提供什么。
  2. 定义返回结构。
  3. 子层算好上交。

代码 / 示例

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)。

概念解释

  • 单边贡献:向上回传。
  • 经过路径:左右都接。

原理流程

  1. 递归求左右单边贡献。
  2. 更新全局最大路径和。
  3. 返回本节点单边贡献。

代码 / 示例

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)。

概念解释

  • 选/不选状态。
  • 父子互斥。

原理流程

  1. 递归左右得两状态。
  2. 本层偷与不偷分别计算。
  3. 返回两值。

代码 / 示例

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 什么关系?

一句话结论

直径是过某节点的最长左右路径之和;递归返回节点高度,全局更新 左高+右高;高度即单边状态,直径在合并层统计;与最大路径和同框架。

概念解释

  • 高度:单边最长边数。
  • 直径:跨节点两单边之和。

原理流程

  1. 递归求左右高度。
  2. 更新全局直径。
  3. 返回本节点高度。

代码 / 示例

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)。

概念解释

  • 多叉:多个孩子。
  • 最长两条:拼经过本节点路径。

原理流程

  1. 递归各孩子得向下长度。
  2. 取最大两条求和更新全局。
  3. 返回最长一条 + 边。

代码 / 示例

遍历孩子,记录 top1/top2 向下长度;ans=max(ans, top1+top2)

常见误区

  • 误区:只取一个孩子路径;正解:直径可跨两个孩子分支。
  • 误区:多叉漏遍历孩子;正解:邻接表全遍历。

追问

  • Q:带权树直径? A:路径长按边权累加。
  • Q:复杂度? A:O(n)。

02.7.2.2-007 树独立集(节点选择不相邻)怎么 DP?

一句话结论

每节点选/不选两状态:选则孩子都不选;不选则孩子各取最优;与打家劫舍 III 同构;求最大权独立集;时间 O(n)。

概念解释

  • 独立集:相邻不同选。
  • 两状态转移。

原理流程

  1. 递归孩子状态。
  2. 选:孩子全不选。
  3. 不选:孩子取最优。

代码 / 示例

选 = 权值 + Σ孩子.not
不选 = Σmax(孩子.选, 孩子.不选)

常见误区

  • 误区:选节点还能选相邻孩子;正解:独立集互斥。
  • 误区:无权值默认 1;正解:按题意权值。

追问

  • Q:最大独立集与最小点覆盖关系? A:二分图中互补,一般树 DP 求解。
  • Q:复杂度? A:O(n)。

02.7.2.2-008 树的最小点覆盖/边覆盖怎么求?

一句话结论

最小点覆盖:每节点选/不选,叶子不选则父必须选;选=1+Σ孩子.not,不选=Σ孩子.选,取根两状态最小;边覆盖按题意匹配边集合,树形/贪心处理。

概念解释

  • 点覆盖:每条边至少一端被选。
  • 转移:父子选择约束。

原理流程

  1. 两状态后序。
  2. 不选当前则孩子必选。
  3. 根取最小。

代码 / 示例

选 = 1 + Σ孩子.not
不选 = Σ孩子.选

常见误区

  • 误区:点覆盖与独立集混淆;正解:约束方向相反,互补关系。
  • 误区:叶子不选无约束;正解:叶子不选则其父承担覆盖。

追问

  • Q:树是二分图吗? A:是,可用二分图匹配求覆盖。
  • Q:复杂度? A:O(n)。

02.7.2.2-009 多子树怎么转二叉树 DP?

一句话结论

多叉树递归遍历所有孩子聚合状态:把孩子状态累加到当前节点的选/不选或最值中;二叉树的左右两支换成孩子列表循环;信息合并方式不变。

概念解释

  • 孩子列表:邻接表。
  • 循环聚合:替代左右分支。

原理流程

  1. 遍历所有孩子递归。
  2. 累加/比较孩子状态。
  3. 生成本节点状态。

代码 / 示例

for (TreeNode c : children) {
    Info ci = dfs(c);
    // 聚合到本节点
}

常见误区

  • 误区:只处理前两个孩子;正解:遍历全部子节点。
  • 误区:邻接表忘排除父节点;正解:有根树递归跳过 parent。

追问

  • Q:无根树怎么定根? A:任选节点 DFS,记录父节点防回跳。
  • Q:多叉状态聚合? A:按题意累加或取最值。

02.7.2.2-010 树形 DP 递归返回值怎么设计?

一句话结论

返回父层所需的最小信息集:需要区分选择就返回选/不选两值,需要高度就返回高度;全局最优可单独用成员变量更新;避免返回冗余信息导致合并复杂。

概念解释

  • 最小信息集。
  • 全局答案旁路更新。

原理流程

  1. 明确父层依赖。
  2. 设计返回结构。
  3. 全局最值旁路记录。

代码 / 示例

// 返回 {选, 不选};ans 在递归中更新

常见误区

  • 误区:返回整棵子树所有信息;正解:只回传父层需要的。
  • 误区:全局变量多线程共享;正解:单次求解局部使用。

追问

  • Q:返回数组还是对象? A:两值可用数组,语义清晰用对象。
  • Q:答案在根状态还是全局? A:按定义,前缀/根状态或旁路最大。

02.7.2.2-011 选/不选两状态为什么是树形 DP 常见模式?

一句话结论

树边约束常表现为父子互斥(偷不相邻、独立集、点覆盖),天然拆成选当前与不选当前两状态;两状态覆盖所有决策,父层据此合并,是最经典的树形 DP 结构。

概念解释

  • 互斥约束。
  • 二元状态。

原理流程

  1. 列父子约束。
  2. 定义选/不选。
  3. 转移互斥关系。

代码 / 示例

选:孩子不选;不选:孩子任选最优

常见误区

  • 误区:把两状态合并成一个最优值;正解:父层需要知道是否选了当前。
  • 误区:状态扩展遗漏;正解:约束多于二元时增加状态类。

追问

  • Q:哪些题是两状态? A:打家劫舍 III、独立集、点覆盖。
  • Q:三状态树形 DP 有吗? A:有,如带颜色/类型约束。

02.7.2.2-012 子树信息怎么自底向上合并?

一句话结论

递归先得到所有子树状态,再在当前节点按规则合并:累加求和、取最值、组合两状态;合并只使用子节点返回值,不再下钻;父节点随后把合并结果上交。

概念解释

  • 自底向上:子先父后。
  • 合并规则:按题意。

原理流程

  1. 子树递归完成。
  2. 聚合孩子结果。
  3. 生成本层状态。

代码 / 示例

sum = Σ孩子.sum;best = max(孩子.best)

常见误区

  • 误区:合并时重新遍历子树;正解:读返回值即可。
  • 误区:合并顺序影响结果;正解:可交换操作顺序无关。

追问

  • Q:合并需要父节点信息吗? A:多数只靠子树与本节点值。
  • Q:合并代价放哪? A:本层计算计入当前状态。

02.7.2.2-013 树形 DP 空节点怎么初始化?

一句话结论

空子树返回基准状态:高度 0、选/不选均 0、不可达按题意;空节点基准使叶子节点转移可直接套用统一公式,避免叶子特判。

概念解释

  • 空基准:叶子的子树。
  • 统一公式。

原理流程

  1. 定义空节点返回值。
  2. 叶子由空基准合并。
  3. 公式对所有节点一致。

代码 / 示例

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)。

概念解释

  • 节点一次。
  • 边遍历一次。

原理流程

  1. 每节点一次递归。
  2. 孩子聚合遍历边。
  3. 栈深为树高。

代码 / 示例

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) 量级。

概念解释

  • 依赖:父子选择关联。
  • 树上分组背包。

原理流程

  1. 后序递归孩子。
  2. 孩子背包并入父节点 DP。
  3. 当前节点选/不选更新。

代码 / 示例

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 计算顺序即后序:先子后父;递归写法天然后序;迭代实现需显式栈记录“子节点已处理”状态位,与后序迭代一致。

概念解释

  • 后序:子→父。
  • 状态位:子完成后合并。

原理流程

  1. 递归压入子节点。
  2. 子层返回后合并。
  3. 父层上交。

代码 / 示例

dfs(left); dfs(right); merge(root)

常见误区

  • 误区:前序就算父层状态;正解:缺子树结果。
  • 误区:迭代忘状态位;正解:标记子节点已返回。

追问

  • Q:树形 DP 能用前序吗? A:依赖子结果的必须后序。
  • Q:层序能做吗? A:自底向上层序也可,但递归后序最自然。

02.7.2.2-017 状态回传与全局最优怎么配合?

一句话结论

需要上交父层的信息走返回值;不向上传递的全局最值(直径、最大路径和)在递归中用成员变量更新;两者分工:返回值服务父层,全局变量记录跨子树答案。

概念解释

  • 回传:父层依赖。
  • 全局:跨节点最优。

原理流程

  1. 区分哪些信息上交。
  2. 返回值封装上交项。
  3. 全局变量旁路更新答案。

代码 / 示例

int ans;
Info dfs(TreeNode r) { ...; ans = max(ans, 跨节点值); return info; }

常见误区

  • 误区:全局最优也塞进返回值;正解:父层用不到的放全局。
  • 误区:多棵树复用全局未清零;正解:每棵树前重置。

追问

  • Q:不用全局变量可以吗? A:可返回含全局最优的结构,但较繁琐。
  • Q:全局变量线程安全? A:单次求解无并发即可。

02.7.2.2-018 多叉树状态聚合有哪些方式?

一句话结论

按题意:求和类累加孩子状态,最值类遍历取最大,组合类(选/不选)分别聚合;遍历所有孩子后生成本节点状态;邻接表递归需排除父节点。

概念解释

  • 聚合:加/取/组合。
  • 防回跳:记录 parent。

原理流程

  1. 遍历孩子。
  2. 按规则聚合。
  3. 生成本层状态。

代码 / 示例

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 常见误区有哪些?

一句话结论

高频错误:前序处理父节点、返回值信息不足、选/不选状态混淆、空节点基准缺失、多叉漏孩子、全局最优与回传混用;按后序、返回结构、空基准、孩子遍历逐项核对。

概念解释

  • 顺序:后序。
  • 状态:返回完整。

原理流程

  1. 核对遍历顺序。
  2. 检查返回信息。
  3. 补空基准与孩子遍历。

代码 / 示例

排查:后序 / 返回结构 / 选不选 / 空基准 / 多叉遍历 / 全局回传

常见误区

  • 误区:二叉树思路套多叉只取两支;正解:遍历全部孩子。
  • 误区:递归深度大未评估;正解:链形 O(n) 注意栈深。

追问

  • Q:结果缺子树贡献先查什么? A:孩子是否递归到、返回值是否被使用。
  • Q:父子约束违反先查什么? A:选/不选转移关系。

02.7.2.2-020 树形 DP 怎么判断该不该用?

一句话结论

问题在树上按父子约束分解、子树独立、答案自底向上合并时用树形 DP;约束是相邻互斥、子树选优、路径跨节点等典型场景;若结构不是树则归其他专题。

概念解释

  • 树上子问题。
  • 自底向上合并。

原理流程

  1. 确认结构是树。
  2. 看子问题是否为子树。
  3. 选后序状态合并。

代码 / 图示

父子约束 / 子树最优 / 跨节点路径 → 树形 DP

常见误区

  • 误区:把线性序列当树做;正解:无层级结构用线性 DP。
  • 误区:图有环仍按树形;正解:有环需先判环或换图算法。

追问

  • Q:二叉树路径题都归树形 DP 吗? A:求子树聚合的是,单纯遍历不是。
  • Q:树形 DP 一般状态数? A:O(n) 节点,单节点常数状态。