Java에서 최소 높이 트리를 구현하는 방법

문제에 필요한 사항

트리는 두 정점이 하나의 경로로만 연결되는 무방향 그래프입니다. 즉, 단순한 순환이 없는 연결된 그래프는 트리입니다.

0부터 n - 1까지 라벨이 붙은 n개의 노드를 포함하는 트리가 제공됩니다. 숫자 n과 n - 1개의 방향이 없는 가장자리가 있는 가장자리 목록이 주어지면(각 가장자리는 레이블 쌍입니다), 여기서 edge[i] = [ai, bi]는 트리의 노드 ai와 bi 사이에 가장자리가 있음을 의미합니다. 가장자리.

트리의 모든 노드를 루트로 선택할 수 있습니다. 노드 x가 루트 노드로 선택되면 결과 트리의 높이를 h로 둡니다. 가능한 모든 트리 중에서 최소 높이(즉, min(h))를 갖는 트리를 최소 높이 트리라고 합니다.

모든 최소 높이 트리를 찾아 루트 노드 레이블 목록을 순서에 관계없이 반환하세요.

트리의 높이는 루트 노드와 리프 노드 사이의 가장 긴 아래쪽 경로에 있는 가장자리 수를 나타냅니다.

예 1:

입력: n = 4, edge = [[1,0],[1,2],[1,3]]
출력: [1]
설명: 다음과 같습니다. 그림에서 루트가 레이블 1을 가진 노드일 때 트리의 높이는 1이며, 이는 유일한 최소 높이 트리입니다.

예 2:

입력: n = 6, 가장자리 = [[3,0],[3,1],[3,2],[3,4],[5,4]]
출력: [3,4]

프롬프트:
1 edges.length == n - 1
0 ai != bi
모두(ai, bi)는 서로 다릅니다
주어진 입력은 트리임이 보장되며 중복된 모서리가 없습니다

문제 해결 아이디어

  위의 두 그림에서, 결론: 문제에서 해결해야 할 것은 트리의 중앙 노드이며, 각 트리에는 2개 이하의 중앙 노드가 있습니다.

  그리고 트리의 중앙 노드를 얻으려면 마지막 레이어가 나올 때까지 FBS 레이어를 레이어별로 잘라낼 수 있습니다(즉, 레이어별로 한 레이어의 아웃 차수로 리프 노드를 잘라냄). 잘라내면 할 수 있습니다. 결과가 출력됩니다!

알고리즘

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<Integer>();
        //如果只有一个节点，则它就是最小高度树
        if(n == 1){
            res.add(0);
            return res;
        }

        //每个节点的邻居数量
        int [] degree = new int[n];
        //每个节点的邻居
        HashMap<Integer,List<Integer>> map = new HashMap<>();

        for(int [] edge : edges){
            int a = edge[0];
            int b = edge[1];

            degree[a]++;
            degree[b]++;

            if(map.get(a) == null){
                map.put(a,new ArrayList<Integer>());//key:节点   value:邻居
            }

            if(map.get(b) == null){
                map.put(b,new ArrayList<Integer>());//key:节点   value:邻居
            }

            map.get(a).add(b);
            map.get(b).add(a);
        }

        //建立队列
        LinkedList<Integer> leafNodes = new LinkedList<Integer>();//表示叶子节点
        //将所有度为1的节点入队
        for(int i = 0;i < degree.length;i++){
            if(degree[i] == 1){
                leafNodes.add(i);
            }
        }

        while(leafNodes.size() > 0){
            res.clear();
            //每一层节点的数量
            int size = leafNodes.size();

            for(int i = 0;i < size;i++){
                int leaf = leafNodes.poll();
                //将当前节点加入到结果集
                res.add(leaf);

                List<Integer> neighbors = map.get(leaf);
                //将出度减一，也就是将最外层的叶子节点剪掉
                for(int neighbor : neighbors){
                    degree[neighbor]--;
                    if(degree[neighbor] == 1){
                        //叶子节点入队
                        leafNodes.add(neighbor);
                    }
                }
            }
        }
        return res;
    }
}

위 내용은 Java에서 최소 높이 트리를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!