题目描述

310. Minimum Height Trees

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Example 1:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Example 2:

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]

Constraints:

\(1 <= n <= 2 * 10^4\)
edges.length == n - 1
\(0 <= a_i, b_i < n\)
\(a_i != b_i\)
All the pairs \((a_i, b_i)\) are distinct.
The given input is guaranteed to be a tree and there will be no repeated edges.

广度优先搜索

思路与算法

题目中给定的含有 n 个节点的树，可以推出含有以下特征：

任意两个节点之间有且仅有一条路径（因为无环）；
树中的共有 n−1 条不同的边；
叶子节点的度为 1，非叶子节点的度至少为 2；
树的高度由根节点到叶子节点的最大距离决定。

最直接的解法是，枚举以每个节点为根构成的树，然后求出该树的高度，所有树的最小高度即为答案，需要的时间复杂度为 \(O(n^2)\)，在此不再描述。

设 \(\textit{dist}[x][y]\)表示从节点 x 到节点 y 的距离，假设树中距离最长的两个节点为 (x,y)，它们之间的距离为 \(\textit{maxdist} = \textit{dist}[x][y]\)，则可以推出以任意节点构成的树最小高度一定为\(minheight=\lceil \frac{maxdist}{2}\rceil\)，且最小高度的树根节点一定在节点 x 到节点 y 的路径上。

首先证明树的高度一定为 \(\textit{minheight} = \Big \lceil \dfrac{\textit{maxdist}}{2} \Big \rceil\)，可以用反证法证明，假设存在节点 z，以节点 z 为根的树的高度 \(h < \textit{minheight}\)，则可以推出：

如果节点 z 存在于从 x 到 y 的路径上，由于 x 与 y 均为叶子节点，则可以知道 x 到 z 距离与 y 到 z 距离均小于\(minheight\)（因为z为根，高度 \(h < \textit{minheight}\)），\(\textit{dist}[x][y] = \textit{dist}[x][z] + \textit{dist}[z][y] \le 2 \times (\Big \lceil \dfrac{\textit{dist}[x][y]}{2} \Big \rceil - 1) < \textit{dist}[x][y]\)，这与 x 到 y 的距离为 \(\textit{dist}[x][y]\)相矛盾；
如果节点 z 不存在于 x 到 y 的路径上，假设 z 到 x 的路径为 \(z \rightarrow \cdots \rightarrow a \rightarrow \cdots \rightarrow x\)，z 到 y 的路径为 \(z \rightarrow \cdots \rightarrow a \rightarrow \cdots \rightarrow y\)，这两个路径之间一定存在公共的交叉点，假设交叉点为 a（以z为根的树中，x，y的公共祖先），则可以知道此时 z 到 x 的距离为 \(\textit{dist}[z][x] = \textit{dist}[z][a] + \textit{dist}[a][x]\)，z 到 y 的距离为 \(\textit{dist}[z][y] = \textit{dist}[z][a] + \textit{dist}[a][y]\)。
由于树的高度小于 \(h < \textit{minheight}\)，注意到节点 z 为根，所以可以推出 \(\textit{dist}[z][a] + \textit{dist}[a][x] < \textit{minheight}\)，\(\textit{dist}[z][a] + \textit{dist}[a][y] < \textit{minheight}\)。
即可以推出 \(\textit{dist}[a][x] + \textit{dist}[a][y] \le 2 \times \textit{minheight} - 2 = 2 \times \Big \lceil \dfrac{\textit{dist}[x][y]}{2} \Big \rceil - 2 < \textit{dist}[x][y]\)，这与 x 到 y 的距离为 \(\textit{dist}[x][y]\)相矛盾；

其次证明最小高度树的根节点一定存在于 x 到 y 的路径上，假设存在节点 z 为根的树，它的最小高度为 \(\textit{minheight}\)，但节点 z 不存在于 x 到 y 之间的路径上：
设 z 到 x 的路径为 \(z \rightarrow \cdots \rightarrow a \rightarrow \cdots \rightarrow x\)，z 到 y 的路径为 \(z \rightarrow \cdots \rightarrow a \rightarrow \cdots \rightarrow y\)，这两个路径之间一定存在公共的交叉点，假设交叉点为 a, 则可以知道此时 z 到 x 的距离为 \(\textit{dist}[z][x] = \textit{dist}[z][a] + \textit{dist}[a][x]\)，z 到 y 的距离为 \(\textit{dist}[z][y] = \textit{dist}[z][a] + \textit{dist}[a][y]\)，由于树的高度 \(h = \textit{minheight}\)，所以可以推出 \(\textit{dist}[z][a] + \textit{dist}[a][x] \le \textit{minheight}\)，\(\textit{dist}[z][a] + \textit{dist}[a][y] \le \textit{minheight}\)（x，y不是叶子节点取小于），由于 z 不在 x 到 y 的路径上，所以可以知道\(\textit{dist}[z][a] \ge 1\)，即可以推出 \(\textit{dist}[a][x] < \textit{minheight}，\textit{dist}[a][y] < \textit{minheight}\)，即可以推出 \(\textit{dist}[a][x] + \textit{dist}[a][y] \le 2 \times \textit{minheight} - 2 = 2 \times \Big \lceil \dfrac{\textit{dist}[x][y]}{2} \Big \rceil - 2 < \textit{dist}[x][y]\)，这与 x 到 y 的距离为 \(\textit{dist}[x][y]\)相矛盾。

综合上述推理，设两个叶子节点的最长距离为 \(\textit{maxdist}\)，可以得到结论最小高度树的高度为 \(\Big \lceil \dfrac{\textit{maxdist}}{2} \Big \rceil\)，且最小高度树的根节点一定存在其最长路径上。假设最长的路径的 m 个节点依次为 \(p_1 \rightarrow p_2 \rightarrow \cdots \rightarrow p_m\) ，最长路径的长度为 m-1，可以得到以下结论：

如果 m 为偶数，此时最小高度树的根节点为 \(p_{\frac{m}{2}}\) 或者 \(p_{\frac{m}{2} + 1}\)，且此时最小的高度为 \(\dfrac{m}{2}\) ；
如果 m 为奇数，此时最小高度树的根节点为 \(p_{\frac{m+1}{2}}\) ，且此时最小的高度为\(\frac{m-1}{2}\) 。

因此我们只需要求出路径最长的两个叶子节点即可，并求出其路径的最中间的节点即为最小高度树的根节点。可以利用以下算法找到图中距离最远的两个节点与它们之间的路径：

以任意节点 p 出现，利用广度优先搜索或者深度优先搜索找到以 p 为起点的最长路径的终点 x；
以节点 x 出发，找到以 x 为起点的最长路径的终点 y；
x 到 y 之间的路径即为图中的最长路径，找到路径的中间节点即为根节点。

上述算法的证明可以参考「算法导论习题解答 9-1」。在此我们利用广度优先搜索来找到节点的最长路径，首先找到距离节点 0 的最远节点 x，然后找到距离节点 x 的最远节点 y，然后找到节点 x 与节点 y 的路径，然后找到根节点。

复杂度分析

时间复杂度：\(O(n)\)，其中 n 是为节点的个数。图中边的个数为 n-1，因此建立图的关系需要的时间复杂度为 \(O(n)\)，通过广度优先搜索需要的时间复杂度为 \(O(n + n - 1)\)，求最长路径的时间复杂度为 \(O(n)\)，因此总的时间复杂度为 \(O(n)\)。

空间复杂度：\(O(n)\)，其中 n 是节点的个数。由于题目给定的图中任何两个顶点都只有一条路径连接，因此图中边的数目刚好等于 n-1，用邻接表构造图所需的空间刚好为 \(O(2 \times n)\)，存储每个节点的距离和父节点均为 \(O(n)\)，使用广度优先搜索时，队列中最多有 n 个元素，所需的空间也为 \(O(n)\)，因此空间复杂度为 \(O(n)\)。

参考代码

class Solution {
public:
    int findLongestNode(int u, vector<int> & parent, vector<vector<int>>& adj) {
        int n = adj.size();
        queue<int> qu;
        vector<bool> visit(n);
        qu.emplace(u);
        visit[u] = true;
        int node = -1;
  
        while (!qu.empty()) {
            int curr = qu.front();
            qu.pop();
            node = curr;
            for (auto & v : adj[curr]) {
                if (!visit[v]) {
                    visit[v] = true;
                    parent[v] = curr;
                    qu.emplace(v);
                }
            }
        }
        return node;
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) {
            return {0};
        }
        vector<vector<int>> adj(n);
        for (auto & edge : edges) {
            adj[edge[0]].emplace_back(edge[1]);
            adj[edge[1]].emplace_back(edge[0]);
        }
        
        vector<int> parent(n, -1);
        /* 找到与节点 0 最远的节点 x */
        int x = findLongestNode(0, parent, adj);
        /* 找到与节点 x 最远的节点 y */
        int y = findLongestNode(x, parent, adj);
        /* 求出节点 x 到节点 y 的路径 */
        vector<int> path;
        parent[x] = -1;
        while (y != -1) {
            path.emplace_back(y);
            y = parent[y];
        }
        int m = path.size();
        if (m % 2 == 0) {
            return {path[m / 2 - 1], path[m / 2]};
        } else {
            return {path[m / 2]};
        }
    }
};

拓扑排序

思路与算法

由于树的高度由根节点到叶子节点之间的最大距离构成，假设树中距离最长的两个节点为 (x,y)，它们之间的距离为 \(\textit{maxdist} = \textit{dist}[x][y]\)，假设 x 到 y 的路径为 \(x \rightarrow p_1 \rightarrow p_2 \rightarrow \cdots \rightarrow p_{k-1} \rightarrow p_k \rightarrow y\)，根据方法一的证明已知最小树的根节点一定为该路径中的中间节点，我们尝试删除最外层的度为 1 的节点 x,y 后，则可以知道路径中与 x,y 相邻的节点 \(p_1, p_k\)此时也变为度为 1 的节点，此时我们再次删除最外层度为 1 的节点直到剩下根节点为止。

可以用反证法证明，删除节点 x, y 之后，节点 \(p_1, p_k\) 一定变为度为 1 的叶子节点，假设删除 x, y之后，节点\(p_1,p_k\)的度不为 1，可以假设 \(p_1\)的度不为 1, 则此时与 \(p_1\) 相邻的节点除了 \(p_2\) 外还有其余节点 q 且 q 不在最长的路径中，此时我们知道在最开始的树中节点 q 的度一定不为 1，与 q 连接的节点为 q'，则此时经过节点 q'的路径 \(\textit{dist}[q'][y] = \textit{dist}[p_1][y] + 2 > \textit{dist}[x][y]\)这与 \(\textit{dist}[x][y]\) 为树中的最长路径相矛盾。

其实可用简单的想一想，使用拓扑排序算法，不断剔除度为1的结点的算法正确性。使用反证法：

无向无环图A在删除度为1的结点后得到无向无环图B。可以证明，图A所成最小高度树TreeA是由图B所成的最小高度树TreeB接上被删除结点后构成的。反证法：图B所成的树TreeB如果不是最小高度树，那么存在图B的最小高度树TreeB’，TreeB’的高度比TreeB更小。那么TreeB’接上被删除结点后高度比TreeA更小，这与TreeA是最小高度树矛盾。
既然图A的最小高度树是由图B的最小高度树接上被删除的结点所成。那么图A的最小高度树的根结点与图B的最小高度树的根结点是相同的，因为，接上被删除的结点不会成为根结点，否则相比不成为根结点的高度还要高1。因此找图A的最小高度树的根结点演变为找图B的最小高度树的根结点。

实际做法如下：

首先找到所有度为 1 的节点压入队列，此时令节点剩余计数 \(\textit{remainNodes} = n\)；
同时将当前 \(\textit{remainNodes}\)计数减去出度为 1 的节点数目，将最外层的度为 1 的叶子节点取出，并将与之相邻的节点的度减少，重复上述步骤将当前节点中度为 1 的节点压入队列中；
重复上述步骤，直到剩余的节点数组 \(\textit{remainNodes} \le 2\) 时，此时剩余的节点即为当前高度最小树的根节点。

参考代码

class Solution {
    vector<vector<int> > graph;
    vector<int> degree;
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        //corner case: no edges
        if (n == 1) {
            return {0};
        }
        build(edges,n);
        queue<int> myQ;
        for(int i = 0;i<n;++i){
            if(degree[i]==1) myQ.push(i);
        }
        int remainNodes = n;
        vector<int> ans;
        //BFS
        while(remainNodes>2){
            int sz = myQ.size();
            remainNodes -= sz ;
            for(int i = 0;i<sz;++i){
                int node = myQ.front(); myQ.pop();         
                // update degree
                for(auto& v: graph[node]){
                    degree[v]--;
                    if(degree[v]==1) myQ.push(v);
                    
                }
            }
            
        }
        while(!myQ.empty()){
            ans.emplace_back(myQ.front());
            myQ.pop();
        }
        return ans;
    }
    //邻接矩阵会超时，改成邻接表!!!
    void build(vector<vector<int>>& edges,int n){
        degree.resize(n,0);
        graph.resize(n);
        for(vector<int>& edge:edges){
            int from = edge[0];
            int to = edge[1];
            graph[from].emplace_back(to);
            graph[to].emplace_back(from);
            degree[to]++;
            degree[from]++;
        }
    }
};

注意事项

由上面分析可知，最终结果一定只有1个或者2个节点。
请使用邻接表表示图，不然会循环超时！

二叉树

AVL Tree

Red Black Tree

B Tree

Interval Trees

加权图最短路径

背包问题

子序列问题

二维图

题目描述

广度优先搜索

思路与算法

复杂度分析

参考代码

拓扑排序

思路与算法

参考代码

注意事项

复杂度分析

题目描述 ​

广度优先搜索 ​

思路与算法 ​

复杂度分析 ​

参考代码 ​

拓扑排序 ​

思路与算法 ​

参考代码 ​

注意事项 ​

复杂度分析 ​

题目描述

广度优先搜索

思路与算法

复杂度分析

参考代码

拓扑排序

思路与算法

参考代码

注意事项

复杂度分析