• LeetCode 310 最小高度树


    题目信息

    LeetoCode地址: . - 力扣(LeetCode)

    题目理解

    可以通过归纳法证明出一棵树的最小高度树可以通过从最外面度为1的叶子节点一层一层向内遍历得到,可以使用一种称为 **中心缩减法**(或称为 **剥洋葱法**)的方法。我们将逐步解释这个方法,并证明其正确性。

    ### 定义和问题陈述
    - **树**:无环连通图
    - **树的高度**:从根节点到任意叶子节点的最长路径。
    - **最小高度树**:使树的高度最小的树。对于给定的无向树,可能存在多个根节点,使得树的高度最小。

    ### 中心缩减法(剥洋葱法)

    这个方法的核心思想是逐步移除树的叶子节点(度为1的节点),直到剩下最后一个或两个节点,这些节点就是树的最小高度树的根。

    ### 证明

    #### 步骤和直观理解

    1. **初始阶段**:
       - 考虑一棵树 T" role="presentation" style="position: relative;">T 和它的所有叶子节点集合 L" role="presentation" style="position: relative;">L

    2. **移除叶子节点**:
       - 移除所有的叶子节点 L" role="presentation" style="position: relative;">L 及其连接的边,形成一个新的子树 T" role="presentation" style="position: relative;">T
       - 移除叶子节点后,新的叶子节点是那些在 T" role="presentation" style="position: relative;">T 中与 L" role="presentation" style="position: relative;">L 相邻的节点。

    3. **重复过程**:
       - 对于新的子树 T" role="presentation" style="position: relative;">T,重复上述步骤,继续移除当前的叶子节点。
       - 这一过程持续进行,直到剩下一个或两个节点为止。

    #### 数学证明

    - **基础情况**:单节点树显然是其自身的最小高度树。
    - **归纳步骤**:
      - 设在移除了一层叶子节点后,新的子树 T" role="presentation" style="position: relative;">T 的高度减少1。
      - 继续移除,直到树的高度不能再减少,这时剩下的一个或两个节点即为树的中心节点。

    #### 详细证明

    1. **叶子节点的性质**:
       - 叶子节点位于树的最外层,其高度为最大高度。
       - 移除叶子节点不会影响其他节点的连接性,因为树是无环连通图,移除叶子节点后剩下的子图依然是一棵树。

    2. **递归缩减的效果**:
       - 移除一层叶子节点后,新的子树 T" role="presentation" style="position: relative;">T 的所有节点的高度都减少1。
       - 如果继续移除叶子节点,最终会缩减到树的中心部分。

    3. **树的中心性质**:
       - 对于树的最小高度树,其根节点到所有叶子节点的路径是最短的。
       - 逐层移除叶子节点的方法保证了树的中心在最后一步被识别出来,因为剩下的一个或两个节点即为树的中心。

    ### 结论

    通过逐层移除树的叶子节点,最终剩下的一个或两个节点即为树的中心节点,这些节点就是形成最小高度树的根节点。因此,树的最小高度树可以通过从最外面度为1的叶子节点一层一层向内遍历得到。

    写法1(BFS)

    时间复杂度: O(n)

    空间复杂度: O(n)

    每一层‘洋葱皮’其实就是树的叶子结点集合,而每一层都是潜在的答案,所以我们要将其缓存起来,直到最后没有其他更内部的洋葱皮!。

    1. class Solution {
    2. public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    3. List<Integer> res = new ArrayList<>();
    4. if (n == 1) {
    5. res.add(0);
    6. return res;
    7. }
    8. int[] degree = new int[n];
    9. ArrayList[] adj = new ArrayList[n];
    10. for (int i = 0; i < n; i++) {
    11. adj[i] = new ArrayList<Integer>();
    12. }
    13. for (int i = 0; i < edges.length; i++) {
    14. int x = edges[i][0], y = edges[i][1];
    15. degree[x]++;
    16. degree[y]++;
    17. adj[x].add(y);
    18. adj[y].add(x);
    19. }
    20. Deque<Integer> queue = new ArrayDeque<>();
    21. for (int i = 0; i < n; i++) {
    22. if (degree[i] == 1) {
    23. queue.offer(i);
    24. }
    25. }
    26. int remainCnt = n;
    27. while (remainCnt > 2) {
    28. int size = queue.size();
    29. remainCnt -= size;
    30. for (int i = 0; i < size; i++) {
    31. int u = queue.poll();
    32. List<Integer> nodes = adj[u];
    33. for (Integer next : nodes) {
    34. degree[next]--;
    35. if (degree[next] == 1) {
    36. queue.offer(next);
    37. }
    38. }
    39. }
    40. }
    41. while (!queue.isEmpty()) {
    42. res.add(queue.poll());
    43. }
    44. return res;
    45. }
    46. }
  • 相关阅读:
    使用docker-compose部署,宿主机可链接使用的redis cluster
    MySQL架构介绍与说明
    uni-app:循环数据点击事件获取每行指定数据(获取参数)
    什么是窃听攻击、XSS攻击、CSRF攻击?
    【Centos】深度解析:CentOS下安装pip的完整指南
    Word插件开发
    疫苗预约系统,疫苗接种管理系统,疫苗预约管理系统毕设作品
    如何发现和处理团队中的问题
    1.0 Python 标准输入与输出
    包埋紫杉醇的Pluronic P85/聚乳酸(PLA-P85-PLA)纳米粒子|制备方法
  • 原文地址:https://blog.csdn.net/veatheroe/article/details/139754943