🌕🌕 310. 最小高度树

难度: 🌕🌕

问题描述

---

解法 - BFS

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // 思路：
        // BFS
        // 拥有最小高度树的根节点只能有 1 个 | 2 个
        // 反证法：假设有 3 个结果，{a, b, c} 均满足是最小高度树，树高 == h
        // 现有 另一个节点 d，那么 d 到 a 的高度 max = h，假设就是 h
        // 1.若是 {b, c} 不在 d --> a 的路径上，那么以 {b, c} 为根节点时，d --> {b, c} 树高必 > h，则 {b, c} 不可能是根节点
        // 2.若是 {b, c} 在 d --> a 的路径上
        //   即 d --> {b, c} --> a, d --> {b, c} 树高比 < h，要保证 {b, c} 为根节点，最小树高为 h
        //   那么必存在另一个点，假设为 e，则以 b 为树高时，e --> b 树高 = h
        //   同样满足 e --> {a, c} --> b 树高 = h
        // 根据 d --> b --> a & e --> a --> b 画出来的关系图只能是 
        // d --> b --> a <-- e 其中 d --> a == e --> b == h
        // 然后还有个 c 节点，它满足 d --> c --> a & e --> c --> b 同样高度 == h
        // 若是 c 不在 d --> b --> a <-- e 链路上，而是另起一条链路，则会成环，此时就不是树了
        // ∴ c 必在 d --> b --> a <-- e 链路上，且在 b --> a 区间内，新链路为 d --> b --> c --> a <-- e
        //    此时，以 c 为根节点，
        //    由于 d --> b --> c --> a == h，∴ d --> c < h 
        //    由于 b --> c --> a <-- e == h，∴ e --> c < h
        //    因此就需要一个新的点 f 满足 f --> c == h
        //    同理，满足 f --> a --> c == h && f --> b --> c == h，由于 a, b 分别在 c 的两端
        //    因此新增的 2 条链路使得 f --> a --> c --> b --> h 成环，不满足条件

        // 如何找到 res？
        // 要想是最小高度树的根节点，那么与这个节点相连的节点数就不能过小
        // BFS 依次找出只与一个节点相连的节点集合，将它们加入队列中，等待删除，同时删除与之相连节点的该条连接数
        // 越靠近中间的节点越是所求

        List<Integer> res = new ArrayList<>();
        // 特殊情况特判
        if(n == 1) {
            res.add(0);
            return res; // 题意中每个节点必有边相连，除非只有一个节点
        }
        int[] array = new int[n]; // 记录对应节点还剩多少条连接
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>(); // 记录节点对应的连接集合
        for(int[] cur: edges) {
            int from = cur[0];
            int to = cur[1];
            array[from] ++;
            array[to] ++;
            if(!map.containsKey(from)) {
                ArrayList<Integer> tmpList = new ArrayList<>();
                map.put(from, tmpList);
            }
            if(!map.containsKey(to)) {
                ArrayList<Integer> tmpList = new ArrayList<>();
                map.put(to, tmpList);
            }
            ArrayList<Integer> list = map.get(from);
            list.add(to);
            map.put(from, list);
            list = map.get(to);
            list.add(from);
            map.put(to, list);
        }
        LinkedList<Integer> queue = new LinkedList<>();
        // 将只有一条边的节点入队
        for(int i = 0; i < n; i ++) {
            if(array[i] == 1) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {
            res = new ArrayList<>(); // 记录最后一轮的队列中的节点
            int size = queue.size();
            for(int i = 0; i < size; i ++) {
                int cur = queue.poll();
                res.add(cur);
                // 找到与 cur 相连的边，减去相连边的连接数
                ArrayList<Integer> list = map.get(cur);
                for(int j: list) {
                    if(j == cur) {
                        continue;
                    } 
                    array[j] --;
                    if(array[j] == 1) {
                        // 去掉 cur 连接后，还剩下一条边，入队
                        queue.offer(j);
                    }
                }
            }
        }
        return res;
    }
}

---

输出