102. Binary Tree Level Order Traversal#

Approach 1 - Recursion#

 1public List<List<Integer>> levelOrder(TreeNode root) {
 2  List<List<Integer>> resultList = new ArrayList<>();
 3
 4  if (root == null) {
 5    return resultList;
 6  }
 7
 8  List<Integer> rootLevelList = new ArrayList<>();
 9  rootLevelList.add(root.val);
10
11  resultList.add(0, rootLevelList);
12
13  levelOrder(root.left, resultList, 1);
14  levelOrder(root.right, resultList, 1);
15
16  return resultList;
17}
18
19private void levelOrder(
20  TreeNode currentRoot,
21  List<List<Integer>> list,
22  int level
23) {
24  if (currentRoot == null) {
25    return;
26  }
27
28  if (list.size() - 1 < level) {
29    list.add(level, new ArrayList<Integer>());
30  }
31
32  List<Integer> levelList = list.get(level);
33  levelList.add(currentRoot.val);
34
35  levelOrder(currentRoot.left, list, level + 1);
36  levelOrder(currentRoot.right, list, level + 1);
37}

Approach 2 - BFS#

 1public List<List<Integer>> levelOrder(TreeNode root) {
 2  List<List<Integer>> result = new ArrayList<>();
 3
 4  if (root == null) {
 5    return result;
 6  }
 7
 8  Queue<TreeNode> q = new LinkedList<>();
 9  q.offer(root);
10
11  while (!q.isEmpty()) {
12    int nodesCount = q.size();
13    List<Integer> nodesInLevel = new ArrayList<>();
14
15    for (int i = 0; i < nodesCount; i++) {
16      if (q.peek().left != null) {
17        q.offer(q.peek().left);
18      }
19
20      if (q.peek().right != null) {
21        q.offer(q.peek().right);
22      }
23
24      nodesInLevel.add(q.poll().val);
25    }
26    result.add(nodesInLevel);
27  }
28
29  return result;
30}