# 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]
]

Note:

in Binary Tree Level Order Traversal II, the requirement is only different in getting the outcome as reverse order, namely bottom-up level order traversal as:

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

## Solution

### Top-down level order traversal

#### Using Recursive - DFS

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
levelOrderHelper(root, 0, result);
return result;
}
void levelOrderHelper(TreeNode root, int depth, List<List<Integer>> result) {
if (root == null) {
return;
}
if (depth == result.size()) {
}
levelOrderHelper(root.left, depth + 1, result);
levelOrderHelper(root.right, depth + 1, result);

}
}

#### Using Queue - BFS

public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {

if(root == null) return wrapList;

queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
}
}
return wrapList;
}
}

### Bottom-up level order traversal

#### DFS - Recursive

public class Solution {
public List < List < Integer >> levelOrderBottom(TreeNode root) {
List < List < Integer >> wrapList = new LinkedList < List < Integer >> ();
levelMaker(wrapList, root, 0);
return wrapList;
}

public void levelMaker(List < List < Integer >> list, TreeNode root, int level) {
if (root == null) return;
if (level >= list.size()) {
}
levelMaker(list, root.left, level + 1);
levelMaker(list, root.right, level + 1);
}
}

#### BFS - Queue

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

if(root == null) return wrapList;

queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();