Level order traversal
A level of a binary tree is all the nodes the same number of steps below the root. The root is level 1, its children level 2, their children level 3.
You get the root of a binary tree. Return its values level by level: a list with one inner list per level, starting with the root's level. Each inner list holds that level's values from left to right, as they appear in a drawing of the tree. An empty tree (root is None) gives [].
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.
root = [1, 2, 3, 4, None, 5, 6]Output[[1], [2, 3], [4, 5, 6]]Level 1 is the root. Level 2 is 2 and 3. Level 3 is 4, the left child of 2, then 5 and 6, the children of 3.
root = [8, None, 5, 2]Output[[8], [5], [2]]8 has only a right child, 5, and 5 has only a left child, 2. Each level holds one node.
root = []Output[]No nodes, so no levels.
0 ≤ number of nodes ≤ 1.3 × 105
-104 ≤ node value ≤ 104
The tree is at most 500 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.