• + 1 comment

    Hello Everyone!

    First post on here so please be gentle.

    I've posted my code below, and would like some suggestions how to optomise it. (I'm aware that it's a pretty basic solution).

    I'm passing the first 10 or so test cases but getting all the later ones wrong.

    Carl

    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    
    public class Solution {
        
        public static int setLeafHeight(int element, int[] parentTree){
            if(parentTree[element] == 0){
                return 0;
            }
            return setLeafHeight(parentTree[element], parentTree) + 1;
            
        }
              
        
        public static int[] findHeights(ArrayList<Integer>[] tree, int[] parentTree){
            int[] heights = new int[tree.length];
            
            for(int i=tree.length-1; i>0; i--){
                if(i==1){
                    heights[i] = 0;
                }
                else if(tree[i].size() ==0){
                    heights[i] = setLeafHeight(i, parentTree);
                }
                else{
                    int max = 0;
                    for(int j=0; j<tree[i].size(); j++){
                        if(heights[tree[i].get(j)]>max){
                            max = heights[tree[i].get(j)];
                        }
                    }
                    heights[i] = max-1;
                }
            }
            
            return heights;        
        }
        
        public static int findSize(int element, ArrayList<Integer>[] tree){
            int size = 1;
            
            if(tree[element].size() == 0){
                size = 1;
            }
            
            else{
                for(int i=0; i<tree[element].size(); i++){
                    size += findSize(tree[element].get(i), tree);
                }
                
            } 
            
            return size;
            
        }
        
        public static int[] findTreeSize(ArrayList<Integer>[] tree){
            int[] sizes = new int[tree.length];
            for(int i=tree.length-1; i>0; i--){
                
                
                if(tree[i].size()==0){
                    sizes[i] = 1;
                } else {
                    sizes[i] = findSize(i, tree);
                }
            }
            return sizes;
        }
        
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            ArrayList<Integer> tree[]=new ArrayList[n+1];
            int[] parentTree = new int[n+1];
            
            for(int i=1; i<=n; i++){
                tree[i] = new ArrayList<Integer>();
            }
            
            
            for(int a0 = 0; a0 < n-1; a0++){
                int x = in.nextInt();
                int y = in.nextInt();
                
                tree[x].add(y);  
                parentTree[y] = x;
            }
                   
            
            int[] heights = findHeights(tree, parentTree);
            int[] sizes = findTreeSize(tree);
            
            
            int sumOfHeights = 0;
            for (int j = 1; j<heights.length; j++){
                sumOfHeights += heights[j];
            }        
            
            double treeLost = 0;
            for(int k=1; k<tree.length; k++){
                for (int l=0; l<tree[k].size(); l++){
                
                treeLost += ((heights[tree[k].get(l)])/(double)sumOfHeights)*sizes[tree[k].get(l)];
    
                }
            }
            
            double treeLeft = ((double)n-treeLost);
            
            System.out.println(treeLeft);
            
    
            in.close();
        }
    }