Java - BFS & DFS


  • 0
    A

    BFS:

    public List<Double> averageOfLevels(TreeNode root) {
            List<Double> ll = new LinkedList<>();       
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            while(!q.isEmpty()){
                int lvl = q.size();
                double sum=0;
                for(int i=0; i<lvl; i++) {
                    if(q.peek().left != null) q.offer(q.peek().left);
                    if(q.peek().right != null) q.offer(q.peek().right);
                    sum+=(double)q.poll().val/lvl;
                }
                ll.add(sum);
            }
            return ll; 
    }
    

    DFS: Maintaining Count of Nodes in another List.

    public List<Double> averageOfLevels(TreeNode root) {
            List<Double> al = new ArrayList<>();
            List<Integer> count = new ArrayList<>();
            traverse(root,0,al,count);
            for(int i=0;i<al.size();i++) al.set(i,al.get(i)/count.get(i));
            return al;
        }
            
    private void traverse(TreeNode node, int lvl, List<Double> al, List<Integer> cnt) {
         if(node!=null){			
    	 if(al.size()==lvl){
                 al.add((double)node.val);
                 cnt.add(1);
             }
             else{
                 cnt.set(lvl, cnt.get(lvl)+1);
                 al.set(lvl, al.get(lvl)+node.val);
             }                
             traverse(node.left,lvl+1, al, cnt);
    	 traverse(node.right,lvl+1, al, cnt);
         }
     }

  • 0

    Simple Solution.

    public List<Double> averageOfLevels(TreeNode root) {
        List<long []> list = new ArrayList<>();
        helper (root, list, 1);
    
        List<Double> ans = new ArrayList<>();
        for (long [] info : list) ans.add (info [0] * 1d/info [1]);
        return ans;
    }
        
    private void helper (TreeNode node, List<long[]> list, int level) {
        if (node == null) return;
        if (list.size () < level) list.add (new long [] { 0, 0 });
        list.get (level - 1) [0] += node.val; 
        list.get (level - 1) [1] ++;
    
        helper (node.left, list, level + 1);
        helper (node.right, list, level + 1);
    }
    

  • 0
    A
    This post is deleted!

Log in to reply
 

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