Reference: Problem I & Problem II
Difficulty: Medium

Problem

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Example: 

1
2
3
4
5
6
7
8
9
10
11
    3
   / \
  9  20
    /  \
   15   7
Output:
[
  [3],
  [9,20],
  [15,7]
]

Analysis

Recursion (preorder)

Expand the result list if the current level is equal to the size of result list. Visiting a node involves putting its value to the corresponding array list of current level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> levelOrder(TreeNode root) {
  List<List<Integer>> result = new ArrayList<>();
  preorder(root, result, 0);
  return result;
}

private void preorder(TreeNode root, List<List<Integer>> result, int level) {
  if (root == null) {
    return;
  }
  if (level == result.size()) { // expand
    result.add(new ArrayList<>());
  }
  result.get(level).add(root.val); // visit
  preorder(root.left, result, level + 1);
  preorder(root.right, result, level + 1);
}

Time: $O(N)$
Space: $O(h + N)$ including result list.

Iteration (BFS)

Not necessary to use one more queue to store the level information.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<List<Integer>> levelOrder(TreeNode root) {
  if (root == null) { // this check is required
    return new ArrayList<>();
  }
  List<List<Integer>> result = new ArrayList<>();
  Queue<TreeNode> queue = new LinkedList<>();
  queue.offer(root);
  int level = 0;
  while (queue.size() > 0) {
    // start the current level
    result.add(new ArrayList<>());

    // queue stores all nodes on the current level
    int levelSize = queue.size();
    for (int i = 0; i < levelSize; ++i) {
      TreeNode node = queue.poll();
      result.get(level).add(node.val);
      // offer its children to the queue
      if (node.left != null) queue.offer(node.left);
      if (node.right != null) queue.offer(node.right);
    }

    ++level;
  }
  return result;
}

Time: $O(N)$
Space: $O(h + N)$ including result list.

Problem II

Return the bottom-up level order traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> levelOrderBottom(TreeNode root) {
  List<List<Integer>> result = new LinkedList<>();
  preorder(root, result, 0);
  return result;
}

private void preorder(TreeNode root, List<List<Integer>> result, int level) {
  if (root == null) {
    return;
  }
  if (level == result.size()) { // expand
    result.add(0, new ArrayList<>());
  }
  result.get(result.size() - level - 1).add(root.val); // visit
  preorder(root.left, result, level + 1);
  preorder(root.right, result, level + 1);
}