# 102. Binary Tree Level Order Traversal (Medium)

https://leetcode.com/problems/binary-tree-level-order-traversal/

Given a binary tree, return the level order traversal 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]
]
```

## Solutions

### 1.

``````class Solution {

public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();

if (root == null) {
return ans;
}

int maxDepth = maxDepth(root);

// For different layer, allocate an ArrayList to hold the values.
for (int i = 0; i < maxDepth; i++) {
}

recurse(root, 0, ans);

return ans;
}

private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}

int left = maxDepth(root.left) + 1;
int right = maxDepth(root.right) + 1;

return Math.max(left, right);
}

private void recurse(TreeNode root, int depth, List<List<Integer>> ans) {
if (root == null) {
return;
}

// Apply pre-order visiting method such that values stored in each layer list
// are arranged in the order from left to right.

recurse(root.left, depth + 1, ans);
recurse(root.right, depth + 1, ans);
}
}
``````

### 2.

``````class Solution {

// How to define the border of each layer when applying BFS? Count the children nodes
// when traverse the parent nodes.

public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();

// return answer of length 0 if root == null
if (root == null) {
return ans;
}

// Employ queue structure to BFS the tree
Queue<TreeNode> queue = new ArrayDeque<>();

// Insert the root of the tree to initialize the queue.

int count = 1;

// Keep the elements visited by BFS order
List<Integer> tmp = new ArrayList<>();

// start BFS
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();

int size = count;
for (int i = 0; i < size; i++) {
TreeNode parent = queue.poll();
count--;

if (parent.left != null) {
count++;
}

if (parent.right != null) {
count++;
}
}

}

return ans;
}
}
``````