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:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]

Example 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]

一開始我的想法是，對(duì)于每一個(gè)點(diǎn)進(jìn)行廣度優(yōu)先遍歷，看哪個(gè)點(diǎn)的深度最小。這樣的方法很直接，但是超時(shí)了

var findMinHeightTrees = function(n, edges) {
    var min = Number.MAX_VALUE;
    var res = [];
    n--;
    while(n>=0) {
        var edgeTemp = edges.concat();
        var p = [n];
        var minTemp = 1;
        var nextLevel = [];
        while(p.length!==0&&minTemp<=min) {
            while (p.length!==0&&minTemp<=min) {
                var index = 0;
                var now = p.shift();
                while (index<edgeTemp.length&&minTemp<=min) {
                    if (edgeTemp[index][0]===now) {
                        nextLevel.push(edgeTemp[index][1]);
                        if (nextLevel.length===1) {
                            minTemp++;
                        }
                        edgeTemp.splice(index,1);
                    } else if (edgeTemp[index][1]===now){
                        nextLevel.push(edgeTemp[index][0]);
                        if (nextLevel.length===1) {
                            minTemp++;
                        }
                        edgeTemp.splice(index,1);
                    } else {
                        index++;
                    }
                }
            }
            p = nextLevel;
            nextLevel = [];
        }
        if (minTemp < min) {
            res = [n];
            min = minTemp;
        } else if (minTemp === min) {
            res.push(n);
        } 
        n--;
    }
    return res;
};

第二種方法比較巧妙，我們一層一層的刪除它的葉子節(jié)點(diǎn)，最后剩下的一個(gè)或兩個(gè)點(diǎn)就是我們要找的。

var findMinHeightTrees = function(n, edges) {
    if (n === 1) return [0];
    //map里鍵是每個(gè)點(diǎn)，值是每個(gè)點(diǎn)的鄰接點(diǎn)組成的Set
    var map = {};
    for (let i = 0;i < edges.length;i++) {
        if (map[edges[i][0]]===undefined) {
            map[edges[i][0]] = new Set();
            map[edges[i][0]].add(edges[i][1]);
        }
        else map[edges[i][0]].add(edges[i][1]);
        if (map[edges[i][1]]===undefined) {
            map[edges[i][1]] = new Set();
            map[edges[i][1]].add(edges[i][0]);
        }
        else map[edges[i][1]].add(edges[i][0]);
    }
    var leaves = [];
    var newLeaves = [];
    //找到當(dāng)前的葉子節(jié)點(diǎn)
    for (let node in map) {
        if (map[node].size===1) 
            leaves.push(parseInt(node));
    }
    while (n>2) {
        n -= leaves.length;
        //我們要?jiǎng)h除當(dāng)前的葉子節(jié)點(diǎn)獲取新的葉子節(jié)點(diǎn)
        //新的葉子節(jié)點(diǎn)只可能是當(dāng)前葉子節(jié)點(diǎn)的父節(jié)點(diǎn)
        //遍歷先的葉子節(jié)點(diǎn)
        for (let i = 0;i < leaves.length;i++){
            let temp;
            //找到它的父節(jié)點(diǎn)，這里雖然用了循環(huán)，但是其實(shí)只有一個(gè)
            for (let j of map[leaves[i]]) {
                temp = j;
            }
            //在這個(gè)父節(jié)點(diǎn)的鄰接點(diǎn)集里刪掉當(dāng)前的子節(jié)點(diǎn)
            map[temp].delete(leaves[i]);
            //如果這個(gè)父節(jié)點(diǎn)的鄰接點(diǎn)集變?yōu)榱?個(gè)，那它就是新的葉子節(jié)點(diǎn)
            if (map[temp].size===1) newLeaves.push(temp);
        }
        leaves = newLeaves;
        newLeaves = [];
    }
    return leaves;
};