310. Minimum Height Trees

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]

一开始我的想法是，对于每一个点进行广度优先遍历，看哪个点的深度最小。这样的方法很直接，但是超时了

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;
};

第二种方法比较巧妙，我们一层一层的删除它的叶子节点，最后剩下的一个或两个点就是我们要找的。

var findMinHeightTrees = function(n, edges) {
    if (n === 1) return [0];
    //map里键是每个点，值是每个点的邻接点组成的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 = [];
    //找到当前的叶子节点
    for (let node in map) {
        if (map[node].size===1) 
            leaves.push(parseInt(node));
    }
    while (n>2) {
        n -= leaves.length;
        //我们要删除当前的叶子节点获取新的叶子节点
        //新的叶子节点只可能是当前叶子节点的父节点
        //遍历先的叶子节点
        for (let i = 0;i < leaves.length;i++){
            let temp;
            //找到它的父节点，这里虽然用了循环，但是其实只有一个
            for (let j of map[leaves[i]]) {
                temp = j;
            }
            //在这个父节点的邻接点集里删掉当前的子节点
            map[temp].delete(leaves[i]);
            //如果这个父节点的邻接点集变为了1个，那它就是新的叶子节点
            if (map[temp].size===1) newLeaves.push(temp);
        }
        leaves = newLeaves;
        newLeaves = [];
    }
    return leaves;
};