树形动态规划中的换根技巧之完整Code

完整Code结合上面的分析我们可以获得代码的基本流程建图第一次 dfs 获得 root 为根的整体状态第二次 dfs 换根操作每次 的统计出答案回归题目统计答案class Solution { private: vectorvectorint grap; private: // 第一轮 dfs // 获取以 root 为根时各个子树的深度 void dfs0(int cur, int from, vectorint deep) { deep[cur] 1; for (int nex : grap[cur]) { if (from nex) { continue; } // 先搜索子树获取子树的状态 dfs0(nex, cur, deep); deep[cur] max(deep[cur], deep[nex] 1); } } // 换根 DP void dfs1(int cur, int from, vectorint deep, vectorint ans) { // 找出最大和次大值 int first 0, second 0; for (int nex : grap[cur]) { int val deep[nex]; if (val first) { second first; first val; } else if (val second) { second val; } } // 1. 记录当前 ans // 记录 cur 的最大值 ans[cur] first 1; for (int nex : grap[cur]) { if (nex from) { continue; } // 2. 维护下一个栈的 nex当前 cur 相对下一个栈的状态 // 更新 cur 的深度 // 这里指的是换到 nex 后 // 目前这个栈的 cur 的深度要相对 nex 栈做主变化 if (deep[nex] ! first) { deep[cur] first 1; } else { deep[cur] second 1; } dfs1(nex, cur, deep, ans); } } public: vectorint findMinHeightTrees(int n, vectorvectorint edges) { grap vectorvectorint(n); for (auto e : edges) { int u e[0], v e[1]; grap[u].push_back(v); grap[v].push_back(u); } vectorint dp(n); dfs0(0, -1, dp); vectorint eachDeep(n); dfs1(0, -1, dp, eachDeep); // 回归到本题找出深度最小的序列 int minn *min_element(eachDeep.begin(), eachDeep.end()); vectorint ans; for (int i 0; i n; i 1) { if (minn eachDeep[i]) { ans.push_back(i); } } return ans; } };复杂度分析两个复杂度均与树的点数成正比时间复杂度 在 dfs0 和 dfs1 中每个点均只被递归到一次。空间复杂度 主要为邻接表维护深度答案的数组。小结回顾一下什么时候会用到换根 DP一般都是需要统计以每个点作为根时整颗树的某种状态。将 的复杂度化为 的优化。注意在换根时考虑好 cur 和 nex 的互相约束需要更新维护什么内容才能进行下一次的递归。对于新手来说建议先去了解普通的树形 DP因为换根 DP 的第一轮 dfs 一般就是基础的树形 DP 操作。因为可以说普通树形 DP 是学习换根 DP 的基础而练习换根 DP 能对普通树形 DP 具有更深刻的理解。