换根dp，LeetCode310. 最小高度树

一、题目

1、题目描述

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

2、接口描述

cpp

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        
    }
};

python3

3、原题链接

310. 最小高度树

二、解题报告

1、思路分析

在不使用最小高度树结论的情况下，即不使用拓扑排序的情况下，我们怎样思考这个问题？

朴素思路，暴力计算每个点为根时的高度，然后就能求出最小高度了

这样需要O(n^2)的时间复杂度，会爆掉

那么如何优化？

我们发现上图中根从x变到y的过程中，x的除去y的子树高度不变，y除去x的子树高度不变

而且x和y的高度变化具有递推关系，也就是说我们可以根据x、y的原高度，计算出换根后的新高度

假设换根前，x子树中最大高度first和次大高度second

那么如果，换根前y就是first，那么换根后x变成second + 1，否则还是first + 1

而y的其它子树高度不变

这也就是说，我们只需要一次dfs以某个节点为根的所有节点的高度，然后进行换根dp就行了

每次换根后，新根只有一个节点的高度需要重新计算这是O(1)就能解决的，然后新根的高度就是所有子树最大高度+1

无论是第一次dfs还是换根dp，每个节点都最多访问一次，所以整体时间复杂度O(n)

2、复杂度

时间复杂度： O(n)空间复杂度：O(n)

3、代码详解

cpp

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int> dep0(n), dep1(n);
        vector<vector<int>> g(n);
        for(auto& p : edges)
            g[p[0]].emplace_back(p[1]), g[p[1]].emplace_back(p[0]);
        function<void(int, int)> dfs0 = [&](int x, int fa){
            dep0[x] = 1;
            for(int y : g[x])
                if(y != fa)
                    dfs0(y, x), dep0[x] = max(dep0[x], dep0[y] + 1);
        };
        function<void(int)> dfs1 = [&](int x){
            int first = 0, second = 0;
            for(int y : g[x])
                if(dep0[y] > first) second = first, first = dep0[y];
                else if(dep0[y] > second) second = dep0[y];
            dep1[x] = first + 1;
            for(int y : g[x])
                if(!dep1[y])
                    dep0[x] = dep0[y] == first ? second + 1 : first + 1, dfs1(y);
        };
        dfs0(0, -1), dfs1(0);
        int mi = *min_element(dep1.begin(), dep1.end());
        vector<int> ret;
        for(int i = 0; i < n; i++)
            if(dep1[i] == mi) ret.emplace_back(i);
        return ret;
    }
};

​python3

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        dep0, dep1 = [0] * n, [0] * n
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        def dfs0(x: int, fa: int):
            dep0[x] = 1
            for y in g[x]:
                if y != fa:
                    dfs0(y, x)
                    dep0[x] = max(dep0[y] + 1, dep0[x])
        def dfs1(x: int):
            first, second = 0, 0
            for y in g[x]:
                if dep0[y] > first:
                    second = first
                    first = dep0[y]
                elif dep0[y] > second:
                    second = dep0[y]
            dep1[x] = first + 1
            for y in g[x]:
                if not dep1[y]:
                    dep0[x] = first + 1 if dep0[y] != first else second + 1
                    dfs1(y)
        dfs0(0, -1)
        dfs1(0)
        mi = min(dep1)
        return [i for i in range(n) if dep1[i] == mi]