Java BFS Solution


  • 35

    Classic bfs problem. At each level, compute the average since you already know the size of the level.

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

  • 1
    Z

    Not sure am I correct or not.
    I think the root is just one node of the tree, but not the whole tree, so q.add(root) just add a TreeNode into the linkedlist.


  • 0

    @zhiwlin Yes, it adds only the root node.


  • 0
    Z

    @jaqenhgar oh my bad, you do recursion by adding the nodes to q, at first I thought the while loop will just run one times ......


  • 0
    B

    Most elegant java solution. Clean code - Cheers.


  • 0
    F

    Almost same code. LOL

    public class Solution {
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> res = new ArrayList();
            if(root == null) return res;
            Queue<TreeNode> queue = new LinkedList();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                double sum = 0;
                for(int i = 0;i < size;i++){
                    TreeNode cur = queue.poll();
                    if(cur.left != null) queue.offer(cur.left);
                    if(cur.right != null) queue.offer(cur.right);
                    sum += cur.val;
                }
                res.add(sum / size);
            }
            return res;
        }
    }
    

  • 0
    J

    Traditional level-order traverse. Upvoted


  • 0
    S

    really clean solution. Thanks.


  • 0

    same idea as me, I use Stack instead.

        public IList<double> AverageOfLevels(TreeNode root) {                
            IList<double> rs = new List<double>();
            Stack<TreeNode> rsk = new Stack<TreeNode>(); 
            rsk.Push(root);
            return helper(rs, rsk);
        }    
        
        public IList<double> helper(IList<double> rs, Stack<TreeNode> rsk)
        {
            if(rsk.Count == 0)return rs;                
            Stack<TreeNode> next = new Stack<TreeNode>();
            double isum = 0;
            double icount = 0;
            while(rsk.Count > 0)
            {
                TreeNode cur = rsk.Pop();
                isum += cur.val;
                icount++;
                if(cur.left != null)next.Push(cur.left);
                if(cur.right != null)next.Push(cur.right);
            }
            rs.Add(isum/icount);                
            return helper(rs, next);
        }

  • 0
    J

    I don't like editorial solution attached to this problem. It creates too many LinkedList objects. My solution creates only one queue and uses null in a queue as a level termination value. But I like your approach better

    public class Solution {
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            double sum = 0;
            long count = 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            queue.add(null);
            while (!queue.isEmpty()) {
                root = queue.poll();
                if (root == null) {
                    if (!queue.isEmpty()) {
                        queue.add(null);
                    }
                    res.add(sum / count);
                    sum = 0;
                    count = 0;
                } else {
                    sum += root.val;
                    count++;
                    if (root.left != null) {
                        queue.add(root.left);
                    }
                    if (root.right != null) {
                        queue.add(root.right);
                    }
                }
            }
            return res;
        }
    }
    

  • 0
    A

    @jaqenhgar I think the root contains all information of the tree, because it would recursive in the beginning of the root, am I right? I am not so sure acturally, please tell me if you are willing to.


  • 0
    A

    Cool. I used a similar algo but with two stacks.

    public List<Double> averageOfLevels(TreeNode root) {
    
    	Deque<TreeNode> stack1 = new LinkedList<>();
    	Deque<TreeNode> stack2 = new LinkedList<>();
    	List<Double> averageList = new ArrayList<>();
    	stack1.push(root);
    	while (!stack1.isEmpty() || !stack2.isEmpty()) {
    		double average = 0;
    		long sum = 0, count = 0;
    		while (!stack1.isEmpty()) {
    
    			TreeNode t = stack1.pop();
    			sum += t.val;
    			count++;
    			if (t.left != null)
    				stack2.push(t.left);
    			if (t.right != null)
    				stack2.push(t.right);
    
    		}
    		if (count != 0) {
    			average = (double) sum / count;
    			averageList.add(average);
    		}
    
    		average = 0;
    		sum = 0;
    		count = 0;
    
    		while (!stack2.isEmpty()) {
    
    			TreeNode t = stack2.pop();
    			sum += t.val;
    			count++;
    			if (t.left != null)
    				stack1.push(t.left);
    			if (t.right != null)
    				stack1.push(t.right);
    
    		}
    		if (count != 0) {
    			average = (double) sum / count;
    			averageList.add(average);
    		}
    	}
    	return averageList;
    
    }

Log in to reply
 

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