beats 100.00% java solution


  • -1
    J

    package MinimumHeightTrees;

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;

    public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    int[] begin=new int[edges.length2+2];
    int[] end=new int[edges.length
    2+2];
    int[] point=new int[edges.length*2+2];
    int[] start=new int[n];
    int[] outer=new int[n];
    if (n==2){
    List<Integer> result=new ArrayList<Integer>();
    result.add(0);
    result.add(1);
    return result;
    }
    int count=0;
    for (int i=0;i<edges.length;i++){
    count++;
    add(edges[i][0],edges[i][1],begin,end,point,start,count);
    outer[edges[i][1]]++;
    count++;
    add(edges[i][1],edges[i][0],begin,end,point,start,count);
    outer[edges[i][0]]++;
    }
    int ans=Integer.MAX_VALUE;
    List<Integer> result=new ArrayList<Integer>();
    Queue<Integer> queue=new LinkedList<Integer>();
    int[] high=new int[n];
    boolean[] bo=new boolean[n];
    for (int i=0;i<n;i++){
    if (outer[i]==1) { queue.offer(i); bo[i]=true; outer[i]=0; high[i]=1;}
    }
    int now=0;
    while (queue.isEmpty()==false){
    now=queue.poll();
    int next=start[now];
    while (next!=0){
    int to=end[next];
    outer[to]--;
    if (outer[to]==1 && bo[to]==false) {queue.add(to); bo[to]=true; outer[to]=0; high[to]=high[now]+1;}
    next=point[next];
    }
    }
    int max=0;
    for (int i=0;i<n;i++)
    if (high[i]>max){
    result.clear();
    result.add(i);
    max=high[i];
    }
    else if (high[i]==max)
    result.add(i);
    return result;

    }
    
    private void add(int i, int j, int[] begin, int[] end, int[] point, int[] start, int count) {
    	begin[count]=i;
    	end[count]=j;
    	point[count]=start[i];
    	start[i]=count;
    }
    
    
    public static void main(String args[]){
    	int n=8;
    	int[][] edges={{1, 0},{1, 2},{2, 3},{0, 4},{4, 6},{6, 7},{4, 5}};
    	Solution so=new Solution();
    	so.findMinHeightTrees(n, edges);
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.