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);
}