point和node 区别（point和node区别）



解题思路

最小高度树的根节点通常位于图的中心位置。如果我们从所有叶子节点开始，不断剥离，最后剩下的一到两个节点就是最佳的根节点选择。这个过程类似于寻找图的中心节点。

具体步骤：

树的性质和高度关系

中心节点的概念

树的中心节点是指从该节点出发到树中所有其他节点的最长路径最短的那些节点。对于任何树结构，中心节点要么只有一个，要么有两个相邻的中心节点。这是因为：

多源 BFS 剥离方法的合理性

多源 BFS 从所有叶子节点同时开始，逐步剥离外层的叶子节点。这个过程实质上是从图的边缘向中心逐步推进，直到找到图的中心位置。这种方法的优点包括：

import java.util.*;

public class Solution {

  public List<Integer> findMinHeightTrees(int n, int[][] edges) {

    if (n == 1) return Collections.singletonList(0);

    // 构建图和度数组

    List<Set<Integer>> graph = new ArrayList<>();

    for (int i = 0; i < n; ++i) {

      graph.add(new HashSet<>());

    }

    for (int[] edge : edges) {

      graph.get(edge[0]).add(edge[1]);

      graph.get(edge[1]).add(edge[0]);

    }

    // 初始化叶子节点队列

    Queue<Integer> leaves = new LinkedList<>();

    for (int i = 0; i < n; ++i) {

      if (graph.get(i).size() == 1) leaves.offer(i);

    }

    // 多源 BFS 剥离叶子节点

    while (n > 2) {

      int size = leaves.size();

      n -= size; // 每次循环中剥离这么多节点

      for (int i = 0; i < size; ++i) {

        int leaf = leaves.poll();

        int neighbor = graph.get(leaf).iterator().next(); // 叶子节点只有一个邻居

        graph.get(neighbor).remove(leaf);

        if (graph.get(neighbor).size() == 1) leaves.offer(neighbor);

      }

    }

    // 返回剩余的节点

    return new ArrayList<>(leaves);

  }

}

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/hd-nodejs/77505.html