leetcode 310. Minimum Height Trees | 310. 最小高度树（图的邻接矩阵DFS / 拓扑排序）

深碍√TFBOYSˉ_ 2022-10-19 04:24 157阅读 0赞

## 题目 ##

[https://leetcode.com/problems/minimum-height-trees/][https_leetcode.com_problems_minimum-height-trees]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 方法1：图的邻接矩阵 DFS（超时） ####

我一想，这不就是个图嘛，于是随手敲出一个 DFS，结果。。超时了。

class Vertex { 
        Integer val;
        List<Integer> next;
    
        public Vertex() { 
            next = new LinkedList<>();
        }
    }
    
    class Solution { 
        public List<Integer> findMinHeightTrees(int n, int[][] edges) { 
            Vertex[] v = new Vertex[n];
            for (int i = 0; i < n; i++) { 
                v[i] = new Vertex();
            }
            for (int i = 0; i < edges.length; i++) { 
                v[edges[i][0]].next.add(edges[i][1]);
                v[edges[i][1]].next.add(edges[i][0]);
            }
            // dfs
            int globalMin = n;
            ArrayList<Integer> result = new ArrayList<>();
            boolean[] visited = new boolean[n];
            for (int i = 0; i < n; i++) { 
                visited[i] = true; // 避免原地转圈（只记录当前路径走过的节点）
                dfs(v, visited, i, 0);
                if (curMax < globalMin) { 
                    result.clear();
                    result.add(i);
                    globalMin = curMax;
                } else if (curMax == globalMin) { 
                    result.add(i);
                }
                curMax = 0;
                visited[i] = false; // 恢复原状，下次再用
            }
            return result;
        }
    
        int curMax = 0;
    
        public void dfs(Vertex[] v, boolean[] visited, int i, int depth) { 
            curMax = Math.max(curMax, depth);
            for (Integer next : v[i].next) { 
                if (!visited[next]) { 
                    visited[next] = true;
                    dfs(v, visited, next, depth + 1);
                    visited[next] = false;
                }
            }
        }
    }

#### 方法2：拓扑排序（Topological Sorting） ####

参考：[https://leetcode.com/problems/minimum-height-trees/solution/][https_leetcode.com_problems_minimum-height-trees_solution]

**Intuition**

First of all, let us clarify some concepts.

> The *distance* between two nodes is the number of edges that connect the two nodes.

Note, normally there could be multiple paths to connect nodes in a graph. In our case though, since the input graph can form a tree from any node, as specified in the problem, there could only be *one path* between any two nodes. In addition, there would be no cycle in the graph. As a result, there would be no ambiguity in the above definition of *distance*.

> The *height* of a tree can be defined as the *maximum distance* between the root and all its leaf nodes.

With the above definitions, we can rephrase the problem as finding out the nodes that are *overall* close to all other nodes, especially the leaf nodes.

> If we view the graph as an *area of circle*, and the leaf nodes as the *peripheral* of the circle, then what we are looking for are actually the *[centroids][]* of the circle, *i.e.* nodes that is close to all the peripheral nodes (leaf nodes).

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

For instance, in the above graph, it is clear that the node with the value `1` is the *centroid* of the graph. If we pick the node `1` as the root to form a tree, we would obtain a tree with the *minimum height*, compared to other trees that are formed with any other nodes.

Before we proceed, here we make one assertion which is essential to the algorithm.

> For the tree-alike graph, the number of centroids is no more than 2.

If the nodes form a chain, it is intuitive to see that the above statement holds, which can be broken into the following two cases:

*  If the number of nodes is even, then there would be two centroids.
 *  If the number of nodes is odd, then there would be only one centroid.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

For the rest of cases, we could prove by *contradiction*. Suppose that we have 3 centroids in the graph, if we remove all the non-centroid nodes in the graph, then the 3 centroids nodes must form a *triangle* shape, as follows:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

Because these centroids are equally important to each other, and they should equally close to each other as well. If any of the edges that is missing from the triangle, then the 3 centroids would be reduced down to a single centroid.

However, the triangle shape forms a *cycle* which is *contradicted* to the condition that there is no cycle in our tree-alike graph. Similarly, for any of the cases that have more than 2 centroids, they must form a cycle among the centroids, which is contradicted to our condition.

Therefore, there cannot be more than 2 centroids in a tree-alike graph.

**Algorithm**

> Given the above intuition, the problem is now reduced down to looking for all the ***centroid*** nodes in a tree-alike graph, which in addition are no more than two.

The idea is that we *trim* out the leaf nodes layer by layer, until we reach the *core* of the graph, which are the centroids nodes.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

Once we trim out the first layer of the leaf nodes (nodes that have only one connection), some of the non-leaf nodes would become leaf nodes.

The trimming process continues until there are only two nodes left in the graph, which are the *centroids* that we are looking for.

The above algorithm resembles the *topological sorting* algorithm which generates the order of objects based on their dependencies. For instance, in the scenario of course scheduling, the courses that have the least dependency would appear first in the order.

In our case, we trim out the leaf nodes first, which are the **farther** away from the centroids. At each step, the nodes we trim out are closer to the centroids than the nodes in the previous step. At the end, the trimming process terminates at the **centroids** nodes.

**Implementation**

Given the above algorithm, we could implement it via the *Breadth First Search* (BFS) strategy, to trim the leaf nodes layer by layer (*i.e.* level by level).

*  Initially, we would build a graph with the *[adjacency list][]* from the input.
 *  We then create a queue which would be used to hold the leaf nodes.
 *  At the beginning, we put all the current leaf nodes into the queue.
 *  We then run a loop until there is only two nodes left in the graph.
 *  At each iteration, we remove the current leaf nodes from the queue. While removing the nodes, we also remove the edges that are linked to the nodes. As a consequence, some of the non-leaf nodes would become leaf nodes. And these are the nodes that would be trimmed out in the next iteration.
 *  The iteration terminates when there are no more than two nodes left in the graph, which are the desired *centroids* nodes.

Here are some sample implementations that are inspired from the post of [dietpepsi][] in the discussion forum.

class Vertex { 
        Set<Integer> neighbors;
        public Vertex() { 
            neighbors = new HashSet<Integer>();
        }
    }
    
    class Solution { 
        public List<Integer> findMinHeightTrees(int n, int[][] edges) { 
            Vertex[] v = new Vertex[n];
            for (int i = 0; i < n; i++) { 
                v[i] = new Vertex();
            }
            // 初始化邻接矩阵
            for (int[] edge : edges) { 
                v[edge[0]].neighbors.add(edge[1]);
                v[edge[1]].neighbors.add(edge[0]);
            }
            // 逐层删掉最外层叶子，类似拓扑排序
            int remain = n;
            List<Integer> leaves = new ArrayList<>();
            for (int i = 0; i < v.length; i++) { 
                if (v[i].neighbors.size() == 1) leaves.add(i);
            }
            while (remain > 2) {  // 最终只有可能剩余2个或1个
                remain -= leaves.size();
                List<Integer> newLeaves = new ArrayList<>();
                for (int i : leaves) { 
                    int nbr = v[i].neighbors.iterator().next(); // 唯一的neighbor
                    v[nbr].neighbors.remove(i); // 要删除v[i]，就要删除它的所有neighbor节点对v[i]的记录
                    if (v[nbr].neighbors.size() == 1)
                        newLeaves.add(nbr);
                }
                leaves = newLeaves;
            }
            if (leaves.size() == 0) leaves.add(0);
            return leaves;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_minimum-height-trees]: https://leetcode.com/problems/minimum-height-trees/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/412d346389a9404ebcdc8a87cfb36099.png
[https_leetcode.com_problems_minimum-height-trees_solution]: https://leetcode.com/problems/minimum-height-trees/solution/
[centroids]: https://en.wikipedia.org/wiki/Centroid
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/b1aeb15eabe94269ad5e4c6a94fefab4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/31a6563f8e154fea9d6982bce572133e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221005/100134d48eed4f4f9dc7f4ef80bb3ad1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20221005/be5702fa0be14a05962fa763fe02e84c.png
[adjacency list]: https://en.wikipedia.org/wiki/Adjacency_list
[dietpepsi]: https://leetcode.com/problems/minimum-height-trees/discuss/76055/Share-some-thoughts
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/0900b8d7e267476e889ec3fe4e72435b.png