最小高度树

朱雀 2022-12-23 13:28 144阅读 0赞

> leetcode 310 题 \[medium\]  
> 中: [最小高度树][Link 1]  
> 英: [Minimum Height Trees][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70_pic_center]![在这里插入图片描述][20201125122804730.png_pic_center]

### 题解 ###

> **核心**：拓扑排序法  
> **时间复杂度**：O(n)  
> **空间复杂度**：O(n)

/** * @param {number} n * @param {number[][]} edges * @return {number[]} */
    var findMinHeightTrees = function(n, edges) { 
        /** * 拓扑排序法 * 步骤：每次删除所有当前入度为1的结点，直到最后剩下的结点数 <= 2 * 原理： * 1. 删除入度为1的结点：相当于剪去所有当前的叶节点，最小高度树的层数必然(仅)下降1层 * (1) 所以最小高度树的高度等于(删除次数 + 剩下结点数)（假设只有一个结点时高度为1） * 2. 最后结点 <= 2 * (1) 最后剩下1个结点：那么该结点为唯一解 * (2) 最后剩下2个结点：以这两个结点为根的树都是最小高度树 * (3) 最后剩下3个结点：那么必然有两个入度为1的结点和一个入度大于1的结点，可再次通过删除所有当前入度为1的结点进而使得树的高度(仅)下降1层 * (4) 最后剩下结点>3，与(3)同理，可以通过剪枝使树高度下降 * * 时间复杂度：O(n)：O(n)（构建入度数组(邻接列表)）+ O(n)（循环删除入度为1的结点） => O(2n) => O(n) * 空间复杂度：O(n)：O(2*(n-1))（邻接列表大小，其实就等于edges中的结点个数） => O(n) */
        // 初始化入度数组（其实就是邻接列表）
        let inDegreeArr = Array.from({ length: n}, ()=>[]);
        let restNodes = Array.from({ length: n}, (v, i)=>i);
    
        for(let i=0, len=edges.length; i<len; i++){ 
            let item = edges[i];
            inDegreeArr[item[0]].push(item[1]);
            inDegreeArr[item[1]].push(item[0]);
        }
    
        // 循环删除入度为1的结点
        while(restNodes.length > 2){ 
            let needToDelete = [];
            for(let len=restNodes.length, i=len-1; i>=0; i--){ 
                if(inDegreeArr[restNodes[i]] && inDegreeArr[restNodes[i]].length === 1){ 
                    needToDelete.push(restNodes[i]);
                    restNodes.splice(i, 1);
                }
            }
            // 一次性删除
            for(let i=0, len=needToDelete.length; i<len; i++){ 
                let node = needToDelete[i];
                let connected = inDegreeArr[node][0];  // 连接的结点
                inDegreeArr[connected].splice(inDegreeArr[connected].indexOf(node), 1);
            }
        }
        // 结果
        return restNodes;
    };

[Link 1]: https://leetcode-cn.com/problems/minimum-height-trees/
[Minimum Height Trees]: https://leetcode.com/problems/minimum-height-trees/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201125122401659.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ==,size_16,color_FFFFFF,t_70#pic_center
[20201125122804730.png_pic_center]: /images/20221120/2312ae7ec5b34558898a546acfa700c9.png