102. Binary Tree Level Order Traversal

Given a binary tree, return thelevel ordertraversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Analysis:

BFS approach, use a queue. Level order traversal, use a counter, decrement on every queue poll, when counter == 0, update counter with current queue size which is the number of elements in the next level.(Remember to enqueue before update counter so that we get all the element for next level in the queue)

Complexity:

Time: O(n)

Space: O(n) - last level will hold half of the elements

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
        {
            return new ArrayList<List<Integer>>();
        }

        List<List<Integer>> returnList = new ArrayList<List<Integer>>();
        List<Integer> levelList = new ArrayList<Integer>();
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        int count = 1;
        queue.offer(root);
        while(!queue.isEmpty())
        {
            TreeNode cur = queue.poll();
            count--;
            levelList.add(cur.val);
            if(cur.left != null)
            {
                queue.offer(cur.left);
            }
            if(cur.right != null)
            {
                queue.offer(cur.right);
            }

            if(count == 0)
            {
                count = queue.size();
                returnList.add(levelList);
                levelList = new ArrayList<Integer>();
            }
        }

        return returnList;

    }
}