教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读本文以公众号「宫水三叶的刷题日记」系列仓库 LogicStack-LeetCode 中 310. 最小高度树中等 的题解为核心骨架完整讲解「树形 DP 换根」这一经典套路先任选一个根如编号 0做第一次 DFS 自底向上求出每个节点「往下」的最大高度与次大高度再做第二次 DFS 自顶向下求出每个节点「往上」的最大高度最终任意节点作为根时的树高就是max(往下, 往上)。读完本文你将掌握所有「树上全节点视角统计类问题」的统一思维框架并能直接套用到仓库中 124. 二叉树中的最大路径和、834. 树中距离之和、2246. 相邻字符不同的最长路径 等同族题目。题目描述与问题本质给定一棵包含n个节点的无向树节点编号为0到n - 1输入数字n以及n - 1条无向边edges[i] [a_i, b_i]。可以任选树中任何一个节点作为根当选择节点x作为根时结果树的高度为h根节点到叶子节点的最长向下路径上的边数。在所有可能的树中具有最小高度min(h)的树称为最小高度树Minimum Height TreesMHT。题目要求返回所有最小高度树的根节点标签列表顺序任意。数据范围与约束1 n 2 × 10^4edges.length n - 1保证是一棵树0 a_i, b_i na_i ! b_i所有边互不相同输入保证有效示例 1n 4, edges [[1,0],[1,2],[1,3]]输出[1]。以节点 1 为根时树高为 1是唯一的最小高度树。示例 2n 6, edges [[3,0],[3,1],[3,2],[3,4],[5,4]]输出[3,4]。这棵树有两个中心节点都构成最小高度树。一个直觉结论无向树的「中心」直径中点就是最小高度树的根。最朴素的暴力做法是枚举每个节点为根各做一次 DFS/BFS复杂度为 $O(n^2)$在 $n$ 高达 $2 \times 10^4$ 时不可行。因此必须用 $O(n)$ 的树形 DP 一次预处理、换根复用计算结果。树形 DP 的核心思想按「方向」划分状态这是一道树形 DP 模板题。树形 DP 的第一要义是随便以某个节点为根把整棵树“拎起来”进行分析通常还会以「方向」作为切入点思考。当确定以某个点为根节点时整棵树的形态唯一固定因此不妨以编号为0的节点作为根节点。假设当前处理到的节点为u它由父节点fa遍历而来将要遍历的子节点为j。树形 DP 问题通常将问题根据「方向」进行划分对于当前节点u根据是否考虑「从fa到u的出边」将其分为「往上」和「往下」两个方向。状态定义f 数组与 g 数组假设通过两次 DFS 预处理出f数组和g数组f[u]在以0号点为根节点的树中以u节点为子树根节点时往下的最大高度g[u]在以0号点为根节点的树中以u节点为子节点时往上的最大高度。那么最终以u为根节点的最大高度为max(f[u], g[u])。对所有节点计算该值后取全局最小值对应的所有节点即为答案。f[u]只需一次简单的 DFS自底向上即可求出。而g[u]的求解稍显复杂它本身也包含「往上」和「往下」两部分对于经过fa后接着往上的部分有贡献g[fa] 11代表fa到u的这条边对于经过fa后转而往下的部分需要判断「fa节点往下的最大值f[fa]」是否由u节点参与而来分两种情况讨论如果f[fa]本身不由u参与那么g[u]应当取fa节点往下的最大值 1如果fa往下的最大值由u节点参与此时不能重复经过u必须使用fa往下的次大值 1来更新g[u]。因此需要对f数组进行拆分拆分为记录「最大值的f1数组」和记录「次大值的f2数组」注意这里的次大值是非严格次大值同时使用p数组记录取得f1[u]时u的子节点j为何值。链式前向星建图题目输入是边列表edges树形 DP 的递归遍历需要一个高效的无向图存储结构。仓库题解统一使用链式前向星数组模拟邻接表进行转存这与 834. 树中距离之和 题解中的做法完全一致是「刷穿 LeetCode」系列在 $O(n)$ 图论问题中的标准模板int N 20010, M N * 2, idx 0; int[] he new int[N], e new int[M], ne new int[M]; void add(int a, int b) { e[idx] b; ne[idx] he[a]; he[a] idx; }hehead数组记录每个节点的第一条出边下标初始化为-1eedge数组记录边的终点nenext数组记录同一起点的下一条边下标因为是无向树每条边需要add(a, b); add(b, a);双向添加所以边数组容量取M N * 2N取20010是因为题目限制n 2 × 10^4稍微留出余量。建图后调用dfs1(0, -1)与dfs2(0, -1)以-1作为根节点0的“虚拟父节点”保证递归不会越界回溯。第一次 DFS自底向上求 f1、f2、pdfs1完成「往下」方向的计算。对于节点u遍历所有子节点j跳过父节点fa递归求得dfs1(j, u)后加1加上u - j这条边得到子节点方向的高度sub再维护三件事若sub f1[u]说明出现新的最大值原来的最大值降级为次大值即f2[u] f1[u]; f1[u] sub; p[u] j;同时用p[u]记录最大值来自哪个子节点否则若sub f2[u]更新非严格次大值f2[u] sub函数返回f1[u]作为以u为根的子树「往下」的最大高度。int dfs1(int u, int fa) { for (int i he[u]; i ! -1; i ne[i]) { int j e[i]; if (j fa) continue; int sub dfs1(j, u) 1; if (sub f1[u]) { f2[u] f1[u]; f1[u] sub; p[u] j; } else if (sub f2[u]) { f2[u] sub; } } return f1[u]; }由于f1/f2/p都由子节点结果推导而来这是一个自下而上的递推过程叶子节点没有子节点天然有f1 f2 0作为递推的基底。第二次 DFS自顶向下求 gdfs2完成「往上」方向的计算核心技巧是用父节点u更新子节点j而非反过来求u——这样可以避免处理根节点fa为空-1时的边界问题。遍历节点u的子节点j根据p[u]判断f1[u]是否由j贡献若p[u] ! j说明u往下的最大值与j无关j可以安全复用该最大值g[j] max(g[j], f1[u] 1)若p[u] j说明u往下的最大值恰恰经过j此时必须退而求其次使用次大值g[j] max(g[j], f2[u] 1)。上述两者覆盖了「往上再往下」的部分最后再补上「往上再往上」的部分g[j] max(g[j], g[u] 1)然后递归进入dfs2(j, u)继续向下传递。void dfs2(int u, int fa) { for (int i he[u]; i ! -1; i ne[i]) { int j e[i]; if (j fa) continue; if (p[u] ! j) g[j] Math.max(g[j], f1[u] 1); else g[j] Math.max(g[j], f2[u] 1); g[j] Math.max(g[j], g[u] 1); dfs2(j, u); } }注意这里的「非严格次大值」f2非常关键。当u的多个子节点并列最大时f2可能与f1相等这恰恰是正确的——因为即使最大值路径经过j仍可能存在另一条同样长的路径不经过j此时用与最大值相等的次大值更新即可保证不遗漏答案。汇总答案O(n) 扫描两次 DFS 完成后所有节点的f1与g均已就绪。第三次线性扫描统计答案ListInteger ans new ArrayList(); int min n; for (int i 0; i n; i) { int cur Math.max(f1[i], g[i]); if (cur min) { min cur; ans.clear(); ans.add(i); } else if (cur min) { ans.add(i); } } return ans;以节点i为根的最小可能高度为max(f1[i], g[i])取所有节点中的最小值min遇到更小值则重置答案列表遇到相等值则追加——这正是题目要求返回所有最小高度树根节点的原因由于树高最小值的上界不超过nmin初始化为n是安全的选择。复杂度分析时间复杂度$O(n)$。两次 DFS 各遍历所有节点与边一次每条无向边正反各访问一次最后的线性扫描也是 $O(n)$空间复杂度$O(n)$。需要he/e/ne三数组存储图$O(n)$以及f1/f2/g/p四个 DP 数组$O(n)$递归栈深度在最坏情况下为链状树的 $O(n)$。补充理解为什么需要 f1 / f2 / p 三件套初次接触「树形 DP」的同学可能对换根过程感到抽象这里再补充说明一下。归根结底以u为根节点的最大深度必然是下面三种情况之一往下进入u的某个子树方向延伸——由f1[u]覆盖往上从u经过fa继续向“上”走——由g[u]覆盖g[u] 1传播到子节点往上再往下从u经过fa后在fa的“上方/侧方”折返进入另一条不经过u的路径——这是换根时最容易出错的情况。其中对f数组的拆分变为f1与f2以及记录取得f1对应的子节点p[i]目的都是为了能够正确统计第 3 种「往上再往下」的情况统计该情况时不能考虑从fa经过u的路径否则路径会重复经过边fa-u因此需要记录一个非严格的次大值f2配合p数组精确判断何时该用次大值。可以这样记忆这套模板的「一拆三」结构数组含义求解方向f1[u]以0为根时u子树「往下」的最大高度自底向上第一次 DFSf2[u]以0为根时u子树「往下」的非严格次大高度自底向上第一次 DFSp[u]取得f1[u]时对应的子节点自底向上第一次 DFSg[u]以0为根时u节点「往上」的最大高度自顶向下第二次 DFS同族题目与仓库中的延伸阅读「树形 DP 换根 / 方向拆分」是极其通用的一类套路在 LogicStack-LeetCode 仓库中多处出现读者可对照学习二叉树中的最大路径和困难把路径拆成「往左、往右、往父」三个方向一次 DFS 求往下路径和第二次 DFS 利用已算好的往下结果推导往上的路径和与本题的两次 DFS 结构同源树中距离之和困难同样以0为根做两次 DFSf[u]为「往下」距离之和、g[u]为「往上」距离之和最终ans[u] f[u] g[u]并把「往上」拆成「往上再往上」与「往上再往下」两部分——与本题的转移设计完全同构相邻字符不同的最长路径困难在定根树题目给定parent数组上记录每个节点的最大与次大子路径合并得到以该节点为最高点的最长路径体现了「最大值 次大值」思想在定根场景的简化形态。上述题目均被收录在仓库的 Index/树形 DP.md 索引表中其中 310 题的推荐指数为最高等级是学习树形 DP 换根模板的首选入口。读者可以在仓库中对照这些题解归纳出「先任选根做一次自底向上 DFS、再做一次自顶向下 DFS、按方向拆状态」的统一解题模板从而一通百通。小结最小高度树问题的核心不在于枚举根节点而在于用两次 DFS 完成「全根视角」的预处理第一次 DFS 自底向上求出每个节点往下含子树内的最大与次大高度第二次 DFS 自顶向下求出每个节点往上的最大高度最终任意节点的最小可能树高为max(f1[u], g[u])。f1 / f2 / p / g四数组配合「链式前向星」建图将暴力 $O(n^2)$ 优化为 $O(n)$同时天然支持多答案输出。掌握本题即掌握了树形 DP 换根这一高频考点的完整套路。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐AlgoNote 题解LeetCode 310 最小高度树——树形 DP 二次遍历换根法详解AlgoNote 题解LeetCode 310 最小高度树——树形 DP 二次遍历换根法详解 本文以 AlgoNote 仓库中的 310. 最小高度树题解 h教程文档知识库LogicStack-LeetCode 树形 DP 专题从定根一遍 DFS 到换根两遍 DFS 的完整方法论LogicStack LeetCode 树形 DP 专题从定根一遍 DFS 到换根两遍 DFS 的完整方法论 导读 本文以 LogicStack LeetCo教程文档树专题四题精讲LogicStack-LeetCode 带你打通树形 DP、换根 DP、构造验证与内向基环树树专题四题精讲LogicStack LeetCode 带你打通树形 DP、换根 DP、构造验证与内向基环树 本文以 Index/树.md https://li教程文档上一篇ZyPlayer你的私人影视管家一个应用搞定全网视频资源下一篇Laravel-Modules 完整贡献指南从新手到核心贡献者的终极教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考