Using BFS with sizing the queue


  • 0
    L

    It is perhaps no-brainer that we need to use a queue for this traversal. The tricky part is sizing the queue in a way that nodes from a particular level are printed first before printing the next level. The trick is to size the queue at each level and print till that the given size becomes zero. Look at the code to understand it better:

    public List<List<Integer>> levelOrder(TreeNode root) {
            if(root==null) {
                return Collections.emptyList();
            }
            
            List<List<Integer>> ll = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while(!queue.isEmpty()) {
                int size = queue.size();
                List<Integer> l = new ArrayList<>();
                while(size>0) {
                    TreeNode node = queue.poll();
                    l.add(node.val);
                    if(node.left!=null) {
                        queue.add(node.left);
                    }
                    if(node.right!=null) {
                        queue.add(node.right);
                    }                 
                    size--;
                }
                ll.add(l);            
            }
            return ll;
        }
    

Log in to reply
 

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