Interview challenge · medium · binary-tree, bfs, queue
Binary Tree Level Order Traversal
El reto
El enunciado va en inglés, igual que en el vídeo.
Given the root of a binary tree, return the values of its nodes level by level: first the root, then its children from left to right, then their children, and so on.
Example
3
/ \
9 20 -> [[3], [9, 20], [15, 7]]
/ \
15 7
empty tree -> []Idea: breadth-first search with a queue. At the start of each round, the queue holds exactly one level: take that many nodes out, record their values and push their children, which form the next level. Time O(n), and the queue holds at most one level at a time.
La solución
# Level Order Traversal - ayotl.dev
from collections import deque
class Node:
def __init__(self, v, l=None, r=None):
self.v, self.l, self.r = v, l, r
def levels(root):
out = []
q = deque([root] if root else [])
# one queue pass per level
while q:
row = []
for _ in range(len(q)):
n = q.popleft()
row.append(n.v)
for c in (n.l, n.r):
if c:
q.append(c)
out.append(row)
return out
t = Node(3, Node(9),
Node(20, Node(15), Node(7)))
print(levels(t))
print(levels(None))
$ python3 binary_tree_level_order_traversal.py
[[3], [9, 20], [15, 7]]
[]