# Question

Formatted question description: https://leetcode.ca/all/102.html

102	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,#,#,15,7},
3
/ \
9  20
/  \
15   7
return its level order traversal as:
[
,
[9,20],
[15,7]
]

@tag-tree


# Algorithm

The typical breadth-first search BFS application, but here is a little more complicated, to separate the numbers of each layer and store them in a two-dimensional vector.

The general idea is basically the same, create a queue, and then put the root node first Go in, then find the left and right child nodes of the root node, then remove the root node.

At this time, the elements in the queue are all the nodes in the next layer. Use a for loop to traverse them, and then store them in a one-dimensional vector to traverse After that, save the one-dimensional vector into the two-dimensional vector

### Note

Use the null insertion method to mark each layer, is one way of marking level ending.

Pay attention to below:

1. The boundary problem of null, eg has only one root=1. Whenever it encounters null, first check whether q is empty. If q is empty, it will be the last, break directly If q is not empty, then offer a null as the end sign of the next layer

2. Note that the implementation of queue uses linkedlist, but arraylist does not work (removeFirst, removeLast are not supported)

# Code

Java

• import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Binary_Tree_Level_Order_Traversal {

public static void main(String[] args) {

}

/**
Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
*/

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

List<List<Integer>> result = new ArrayList<List<Integer>>();

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

// @note: use level count as marker of each level, instead of adding an extra null as marker
int currentLevelCount = 0;
int nextLevelCount = 0;

// initialization
q.offer(root);
currentLevelCount++;

List<Integer> currentLevelList = new ArrayList<>();
while (!q.isEmpty()) {
TreeNode currentNode = q.poll();
currentLevelCount--;

// enqueue
if (currentNode.left != null) {
q.offer(currentNode.left);
nextLevelCount++;
}
if (currentNode.right != null) {
q.offer(currentNode.right);
nextLevelCount++;
}

// check if end of current level
if (currentLevelCount == 0) {
currentLevelCount = nextLevelCount;
nextLevelCount = 0;

// add this level int list to result
currentLevelList.clear();
}
}

return result;
}
}

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

List<List<Integer>> list = new ArrayList<List<Integer>>();

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

sk.offer(root);
sk.offer(null);// @note: use null as marker for end of level

List<Integer> oneLevel = new ArrayList<>();
while (!sk.isEmpty()) {

TreeNode current = sk.poll();

if (current == null) {
List<Integer> copy = new ArrayList<>(oneLevel);

// clean after one level recorded
oneLevel.clear();// @memorize: this api

// @note:@memorize: if stack is now empty then DO NOT add null, or else infinite looping
if (!sk.isEmpty()) {
}

continue;
}

// @note:@memorize: since using null as marker, then must avoid adding null when children are null
// sk.offer(current.left);
// sk.offer(current.right);
if (current.left != null) {
sk.offer(current.left);
}
if (current.right != null) {
sk.offer(current.right);
}

}

return list;
}
}

}

• // OJ: https://leetcode.com/problems/binary-tree-level-order-traversal/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> ans;
queue<TreeNode*> q{ {root} };
while (q.size()) {
ans.emplace_back();
for (int cnt = q.size(); cnt--; ) {
auto n = q.front();
q.pop();
ans.back().push_back(n->val);
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
}
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque

class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
ans = [[root.val]]
queue = deque([root])
while queue:
levelans = []
for _ in range(0, len(queue)):
root = queue.popleft()
if root.left:
levelans.append(root.left.val)
queue.append(root.left)
if root.right:
levelans.append(root.right.val)
queue.append(root.right)
if levelans:
ans.append(levelans)
return ans