Interview challenge · easy · binary-tree, recursion, dfs
Invert Binary Tree
El reto
El enunciado va en inglés, igual que en el vídeo.
Given the root of a binary tree, invert the tree (mirror it, so every left child becomes a right child and vice versa) and return its root.
Example
4 4
/ \ / \
2 7 -> 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1Idea: recursion. Inverting a tree is swapping the two children of the root and inverting each subtree. Time O(n), space O(h) for the call stack.
La solución
# Invert Binary Tree - ayotl.dev
class T:
def __init__(self, v, l=None, r=None):
self.v, self.l, self.r = v, l, r
def invert(t):
if t:
# swap the children, inverted
t.l, t.r = invert(t.r), invert(t.l)
return t
def levels(t):
# read the tree level by level
out, q = [], [t]
while q:
n = q.pop(0)
out.append(n.v)
q += [c for c in (n.l, n.r) if c]
return out
root = T(4, T(2, T(1), T(3)),
T(7, T(6), T(9)))
print(levels(root))
print(levels(invert(root)))
$ python3 invert_binary_tree.py
[4, 2, 7, 1, 3, 6, 9]
[4, 7, 2, 9, 6, 3, 1]