# 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:
[
[3],
[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)

Java