310. 最小高度树（JS实现）

忘是亡心i 2022-11-27 15:59 141阅读 0赞

## 1 题目 ##

> 对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。  
> 格式  
> 该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。  
> 你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， \[0, 1\]和 \[1, 0\] 是相同的，因此不会同时出现在 edges 里。  
> 示例 1:  
> 输入: n = 4, edges = \[\[1, 0\], \[1, 2\], \[1, 3\]\]  
> 0  
> |  
> 1  
> /  
> 2 3  
> 输出: \[1\]  
> 示例 2:  
> 输入: n = 6, edges = \[\[0, 3\], \[1, 3\], \[2, 3\], \[4, 3\], \[5, 4\]\]  
> 0 1 2  
> \\ | /  
> 3  
> |  
> 4  
> |  
> 5  
> 输出: \[3, 4\]  
> 说明:  
> 根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。  
> 树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

链接：https://leetcode-cn.com/problems/minimum-height-trees

## 2 思路 ##

**这道题考察图的遍历，每次从图的最外层节点开始，删除图外层节点（入度为1的节点），直到图中没有节点，最后一次删除的节点就是最内层的根节点**

## 3代码 ##

/** * @param {number} n * @param {number[][]} edges * @return {number[]} */
    var findMinHeightTrees = function(n, edges) { 
        if (edges.length === 0) {    //对于没有边的情况，每个节点都是根节点
            let res = [];
            for (let i=0; i<n; i++) { 
                res.push(i);
            }
            return res;
        }
        const map = { };
    
        for (let edge of edges) {     //建立图结构
            if (!map[edge[0]]) { 
                map[edge[0]] = [];
                map[edge[0]].len = 0;
            }
            if (!map[edge[1]]) { 
                map[edge[1]] = [];
                map[edge[1]].len = 0;
            }
            map[edge[0]].push(edge[1]);
            map[edge[1]].push(edge[0]);
            map[edge[0]].len++;
            map[edge[1]].len++;
        }
    
        let arr = Object.keys(map).filter(key => map[key].len === 1);
    
        let temp = [];
        let visited = { };
        let res = arr.slice();
        while(arr.length > 0 || temp.length > 0) { 
            if (arr.length === 0) { 
                arr = temp;
                temp = [];
                res = arr.slice();
            }
            let p = arr.shift();
            if (visited[p]) continue;
            visited[p] = true;
            for (let edge of map[p]) {    //将下一次外层节点推入
                if (--map[edge].len === 1) temp.push(edge);
            }
        }
    
        return res;
    };