Binary Tree Level Order Traversal

mediumSave

Binary TreeBreadth-First SearchTree

Given a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

Return its level order traversal as:

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

Example 1

Input

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

Output

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

Explanation. Level order traversal splits the nodes into levels according to their depth in the tree.

Example 2

Input

[
  [
    1
  ]
]

Output

[[1]]

Explanation. A single node tree only has one level with one node.

Example 3

Input

[
  []
]

Output

[]

Explanation. An empty tree returns an empty traversal result.

Follow-up: Can you solve the problem iteratively instead of using recursion?

Constraints:

The number of nodes in the tree is in the range `[0, 2000]`. Each node's value is an integer between `-1000000` and `1000000`.