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

# Code

• 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;
}
}

}

############

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
List<Integer> t = new ArrayList<>();
for (int n = q.size(); n > 0; --n) {
TreeNode node = q.poll();
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
}
return ans;
}
}

• // 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:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
t = []
for _ in range(len(q)):
node = q.popleft()
t.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(t)
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


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) (ans [][]int) {
if root == nil {
return
}
q := []*TreeNode{root}
for len(q) > 0 {
t := []int{}
for n := len(q); n > 0; n-- {
node := q[0]
q = q[1:]
t = append(t, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, t)
}
return
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function levelOrder(root: TreeNode | null): number[][] {
const res = [];
if (root == null) {
return res;
}
const queue = [root];
while (queue.length != 0) {
const n = queue.length;
res.push(
new Array(n).fill(null).map(() => {
const { val, left, right } = queue.shift();
left && queue.push(left);
right && queue.push(right);
return val;
}),
);
}
return res;
}


• /**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
let ans = [];
if (!root) {
return ans;
}
let q = [root];
while (q.length) {
let t = [];
for (let n = q.length; n; --n) {
const { val, left, right } = q.shift();
t.push(val);
left && q.push(left);
right && q.push(right);
}
ans.push(t);
}
return ans;
};


• // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut res = vec![];
if root.is_none() {
return res;
}
let mut queue: VecDeque<Option<Rc<RefCell<TreeNode>>>> = vec![root].into_iter().collect();
while !queue.is_empty() {
let n = queue.len();
res.push(
(0..n)
.into_iter()
.map(|_| {
let mut node = queue.pop_front().unwrap();
let mut node = node.as_mut().unwrap().borrow_mut();
if node.left.is_some() {
queue.push_back(node.left.take());
}
if node.right.is_some() {
queue.push_back(node.right.take());
}
node.val
})
.collect(),
);
}
res
}
}