2024.3.17力扣每日一题——最小高度树

题目来源

力扣每日一题；题序：310

我的题解

方法一 深度优先遍历

从每一个节点开始进行深度优先遍历并计算以该节点为根节点的树的深度，使用哈希表存储对应深度有哪些节点，最后取出key最小对应的value的作为结果。超时。

时间复杂度：O($n^2$)
空间复杂度：O(n)

TreeMap<Integer,Set<Integer>> map=new TreeMap<>();
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<Integer>[] g=createTree(n,edges);
    for(int i=0;i<n;i++){
        int minDeep=dfs(g,i,i,-1,1);
        System.out.println(minDeep);
        Set<Integer> l=map.getOrDefault(minDeep,new HashSet<>());
        l.add(i);
        map.put(minDeep,l);
    }
    return new ArrayList<>(map.firstEntry().getValue());
}
public List<Integer>[] createTree(int n,int[][] edges){
    List<Integer>[] g=new ArrayList[n];
    for(int i=0;i<n;i++){
        g[i]=new ArrayList<>();
    }
    for(int[] t:edges){
        int from = t[0];
        int to = t[1];
        g[from].add(to);
        g[to].add(from);
    }
    return g;
}
public int  dfs(List<Integer>[] g,int root,int cur,int pre,int deepth){
    int minDeep=0;
    for(int next:g[cur]){
        if(next!=pre){
            int t=dfs(g,root,next,cur,deepth+1);
            minDeep=Math.max(minDeep,t);
        }
    }
    return minDeep+1;
}

由于一定是树，所以具有最小深度的根节点只有可能最多两个节点作为个根时的深度是相同的。所以，可以求该图中最长的直径，中间节点就是需要求的根节点。所以，不用对所有节点都进行深度优先遍历，只需要遍历两个节点就行了。
时间复杂度：O(n)
空间复杂度：O(n)

//优化版本
TreeMap<Integer,Set<Integer>> map=new TreeMap<>();
List<Integer> path=new ArrayList<>();
int deep=0;
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<Integer>[] g=createTree(n,edges);
    //优化的地方
    List<Integer> p=new ArrayList<>();
    int x=0;
    p.add(x);
    dfs(g,x,-1,1,p);

    p=new ArrayList<>();
    int y=path.get(path.size()-1);
    p.add(y);
    dfs(g,y,-1,1,p);
    int sz=path.size();
    if(sz%2==0){
        return path.subList(sz/2-1,sz/2+1);
    }else{
        return path.subList(sz/2,sz/2+1);
    }
}
public List<Integer>[] createTree(int n,int[][] edges){
    List<Integer>[] g=new ArrayList[n];
    for(int i=0;i<n;i++){
        g[i]=new ArrayList<>();
    }
    for(int[] t:edges){
        int from = t[0];
        int to = t[1];
        g[from].add(to);
        g[to].add(from);
    }
    return g;
}
public void  dfs(List<Integer>[] g,int cur,int pre,int deepth,List<Integer> p){
    if(deepth>deep){
        path=new ArrayList<>(p);
        deep=deepth;
    }
    for(int next:g[cur]) {
        if (next != pre) {
            p.add(next);
            dfs(g, next, cur, deepth + 1, p);
            p.remove(p.size() - 1);
        }
    }
}

方法二 广度优先遍历

在方法一的优化版本基础上，也可以采用广度优先遍历来求最长直径。

时间复杂度：O(n)
空间复杂度：O(n)

TreeMap<Integer,Set<Integer>> map=new TreeMap<>();
List<Integer> path=new ArrayList<>();
int deep=0;
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<Integer>[] g=createTree(n,edges);
    //变化之处在于采用广度优先遍历求最长直径
    int x=0;
    bfs(g,x);
    int y=path.get(path.size()-1);
    bfs(g,y);
    int sz=path.size();
    if(sz%2==0){
        return path.subList(sz/2-1,sz/2+1);
    }else{
        return path.subList(sz/2,sz/2+1);
    }
}
public List<Integer>[] createTree(int n,int[][] edges){
    List<Integer>[] g=new ArrayList[n];
    for(int i=0;i<n;i++){
        g[i]=new ArrayList<>();
    }
    for(int[] t:edges){
        int from = t[0];
        int to = t[1];
        g[from].add(to);
        g[to].add(from);
    }
    return g;
}
public void bfs(List<Integer>[] g,int cur){
    Queue<Integer> queue=new LinkedList<>();
    queue.offer(cur);
    int[] parent=new int[g.length];
    //记录路径
    parent[cur]=-1;
    boolean[] visited=new boolean[g.length];
    visited[cur]=true;
    //最后一层的节点
    int end=cur;
    while(!queue.isEmpty()){
        int sz=queue.size();
        for (int i = 0; i < sz; i++) {
            int t=queue.poll();
            boolean f=false;
            for(int next:g[t]){
                if(visited[next])
                    continue;
                parent[next]=t;
                visited[next]=true;
                queue.offer(next);
                f=true;
            }
            if(!f)
                end=t;
        }
    }
    path.clear();
    while(end!=-1){
        path.add(0,end);
        end=parent[end];
    }
}

方法三 拓扑排序

最小深度也可以看做是一直删除叶子节点，最后剩下的一个或者两个节点就是满足条件的节点。这种每次删除叶子节点的操作实质就是拓扑排序。

时间复杂度：O(n)
空间复杂度：O(n)

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
	//注意：使用拓扑排序需要将只有一个节点的情况单独考虑
    if(n==1)
        return Arrays.asList(0);
    int[] tp=new int[n];
    List<Integer>[] g=createTree(n,edges,tp);
    Queue<Integer> queue=new LinkedList<>();
    for(int i=0;i<n;i++){
        if(tp[i]==1)
            queue.offer(i);
    }
    return tpFunc(g,tp,n,queue);
}
public List<Integer>[] createTree(int n,int[][] edges,int[] tp){
    List<Integer>[] g=new ArrayList[n];
    for(int i=0;i<n;i++){
        g[i]=new ArrayList<>();
    }
    for(int[] t:edges){
        int from = t[0];
        int to = t[1];
        g[from].add(to);
        g[to].add(from);
        tp[from]++;
        tp[to]++;
    }
    return g;
}
public List<Integer> tpFunc(List<Integer>[] g,int[] tp,int remain,Queue<Integer> queue){
    List<Integer> res=new ArrayList<>();
    while(remain>2){
        int sz=queue.size();
        remain-=sz;
        for(int i=0;i<sz;i++){
            int t=queue.poll();
            for(int next:g[t]){
                tp[t]--;
                tp[next]--;
                if(tp[next]==1)
                    queue.offer(next);
            }
        }
        
    }
    while(!queue.isEmpty()){
        res.add(queue.poll());
    }
    return res;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~