How to implement minimum height tree in Java

Question requirements

A tree is an undirected graph in which any two vertices are connected by only one path. In other words, any connected graph without simple cycles is a tree.

You are given a tree containing n nodes, labeled 0 to n - 1 . Given a number n and an edges list with n - 1 undirected edges (each edge is a pair of labels), where edges[i] = [ai, bi] means that there is an edge between nodes ai and bi in the tree Undirected edge.

You can select any node in the tree as the root. When node x is selected as the root node, let the height of the result tree be h. Among all possible trees, the tree with the minimum height (i.e., min(h)) is called the minimum height tree .

Please find all minimum height trees and return their root node label list in any order.

The height of a tree refers to the number of edges on the longest downward path between the root node and leaf nodes.

Example 1:

Input: n = 4, edges = [[1,0],[1,2],[1,3] ]
Output: [1]
Explanation: As shown in the figure, when the root is the node with label 1, the height of the tree is 1, which is the only minimum height tree.

Example 2:

Input: n = 6, edges = [[3,0],[3,1],[3 ,2],[3,4],[5,4]]
Output: [3,4]

##Prompt:

1 edges.length == n - 1
0 ai != bi
All (ai, bi) are different from each other
The given input is guaranteed to be a tree, and there will be no duplicate edges

Problem-solving ideas

  From the above two graphs, we can draw the conclusion: What needs to be solved in the problem is the central node in the tree, and each tree will have no more than two central nodes.

  And if we want to get the central node in the tree, we can FBS layer by layer (that is, pruning the leaf nodes with an out-degree of one layer by layer) until the last layer is cut. , you can output the result!

Algorithm

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;
    }
}

The above is the detailed content of How to implement minimum height tree in Java. For more information, please follow other related articles on the PHP Chinese website!