[LeetCode] 310. Minimum Height Trees

轉自LeetCode

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges(each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1 :

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

        0
        |
        1
       / \
      2   3 

Output: [1]

Example 2 :

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

Note:

• According to the definition of tree on Wikipedia: “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.”
• The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

<Solution>

想法如下

• 這題的思路和 topological sorting 有點類似。先從一個數列來看，找到一個位置，離兩端的距離有最短值，那個位置就是在中間的位置 (如果數列長度是偶數的話，那就是中間那兩個位置)，所以這題要找的，就是在最長路徑上的中間位置

• 在數列上，可以用兩個指標分別兩端出發，當兩個指標指在同一個位置，或是相隔 1，那麼就是要找的答案

• 這題的 input 是一個無向圖，利用 topological sorting 的想法來看，可以先找到最邊緣，也就是只和一個節點有 edge 的節點，來當作起端，就像是在數列上，是從兩端開始，在無向圖上，就找到最邊緣的 leaf node，這樣才是在最長路徑上找

• 從 leaf node 出發，然後把它和它相連 node 之間的 edge，從無向圖中刪除，看看是否有找到新的 leaf node，就這樣一層一層向中間邁進

• 上面這個步驟，終止的條件在於 n <= 2。如同前面提到的，這題的答案會是中間那個位置(長度是奇數時)，或是中間那兩個位置(長度是偶數時)，所以每次歷遍 leaf node 的時候，都將 n 減掉當下 leaf node 的個數

code 如下

Java(參考解法)

Kotlin