JAVA程序设计：最小高度树（LeetCode：310）

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。

示例 1:

输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        |

        1

       / \

      2   3 

输出: [1]

示例 2:

输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2

      \ | /

        3

        |

        4

        |

        5 

输出: [3, 4]

说明:

 根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

思路：

方法一：DFS（超时）

import java.awt.Paint;
import java.awt.Point;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.nio.charset.Charset;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;
import java.util.Vector;


class Solution {
	Vector<Integer>[] q;
	int nowdepth=Integer.MAX_VALUE;
	int mindepth=Integer.MAX_VALUE;
	List<Integer> ans=new ArrayList<>();
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    	if(n==1)
    	{
    		ans.add(0);
    		return ans;
    	}
        q=new Vector[n];
        int x=edges.length;
        if(x==0 || n==0) return ans;
        int y=edges[0].length;
        if(y==0) return ans;
        for(int i=0;i<n;i++)
        	q[i]=new Vector();
        for(int i=0;i<x;i++)
        {
        	q[edges[i][0]].add(edges[i][1]);
        	q[edges[i][1]].add(edges[i][0]);
        }
        for(int i=0;i<n;i++)
        {
        	nowdepth=dfs(i,-1);
        	if(mindepth>=nowdepth)
        	{
        		if(mindepth>nowdepth)
        			ans.clear();
        		ans.add(i);
        		mindepth=nowdepth;
        	}
        }
        return ans;
    }
    
    private int dfs(int u,int fa)
    {
    	int ret=0;
    	for(int i=0;i<q[u].size();i++)
    	{
    		int v=q[u].get(i);
    		if(v==fa)
    			continue;
    		ret=Math.max(ret, dfs(v,u));
    	}
    	return ret+1;
    }
}
           

方法二：拓扑排序

可以证明，最后剩下的能满足的树根不会多于两个，并且一定是入度最大的呢几个。。。。因此我们采用拓扑排序搞就ok。

import java.util.Vector;


class Solution {
	Vector<Integer>[] q;
	int[] inagree;
	Queue<Integer> queue;
	boolean[] inqueue;
	List<Integer> ans=new ArrayList<>();
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    	if(n<=2)
    	{
    		for(int i=0;i<n;i++)
    			ans.add(i);
    		return ans;
    	}
    	
    	inagree=new int[n];
    	inqueue=new boolean[n];
    	queue=new LinkedList();
        q=new Vector[n];
        for(int i=0;i<n;i++)
        {
        	q[i]=new Vector();
        	inqueue[i]=false;
        }
        
        for(int i=0;i<edges.length;i++)
        {
        	q[edges[i][0]].add(edges[i][1]);
        	q[edges[i][1]].add(edges[i][0]);
        	inagree[edges[i][0]]++;
        	inagree[edges[i][1]]++;
        }
        
        for(int i=0;i<n;i++)
        	if(inagree[i]==1)
        		queue.add(i);
        
        while(n>2)
        {
        	int size=queue.size();
        	n-=size;
        	for(int i=0;i<size;i++)
        	{
        		int top=queue.poll();
        		inqueue[top]=true;
        		inagree[top]--;
        		for(int j=0;j<q[top].size();j++)
        		{
        			inagree[q[top].get(j)]--;
        			if(inagree[q[top].get(j)]==1)
        				queue.add(q[top].get(j));
        		}
        	}
        }
        
        n=inqueue.length;
        for(int i=0;i<n;i++)
        	if(!inqueue[i])
        		ans.add(i);
        
        return ans;
    }
}