Espelhar uma árvore binária
A missão
Problema
Um motor de layout guarda uma página como uma árvore binária, e idiomas escritos da direita para a esquerda precisam do layout inteiro invertido. Dada a raiz de uma árvore binária, troque os filhos esquerdo e direito de todos os nós para que a árvore vire a própria imagem espelhada, e retorne a raiz. A árvore tem até 100 nós. Os exemplos mostram o resultado lido nível a nível, da esquerda para a direita.
Exemplos
Input: tree = 4, left 2 (children 1 and 3), right 7 (children 6 and 9)
Output: [4, 7, 2, 9, 6, 3, 1]
Por quê: o 7 agora fica à esquerda, e todo nível é lido de trás para frente
Input: tree = 2, left 1, right 3
Output: [2, 3, 1]
Input: tree = empty
Output: []
Por quê: edge case: não há nada para inverter
Dicas
0 / 3
Inverter a árvore inteira é o mesmo que inverter cada subárvore e depois trocar as duas subárvores da raiz.
Uma árvore vazia é o próprio espelho, e isso dá à recursão o seu caso base.
Em cada nó, troque node.left e node.right e depois espelhe os dois filhos. A ordem entre a troca e as chamadas recursivas não importa, desde que todo nó receba a sua troca.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(h)
Restrições
- n ≤ 100 nodes
Solução
O espelho de uma árvore é a raiz dela com a subárvore direita espelhada à esquerda e a subárvore esquerda espelhada à direita, então a própria definição já é uma recursão. Cada chamada troca os dois filhos do seu nó e segue recursivamente pelos dois; uma subárvore vazia retorna na hora. Todo nó é trocado exatamente uma vez, então o tempo é O(n), e o espaço é O(h) para a recursão em uma árvore de altura h.
from collections import deque
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def mirror(node):
if node is None:
return None
node.left, node.right = mirror(node.right), mirror(node.left) # swap flipped halves
return node
def levels(root):
out, q = [], deque([root] if root else [])
while q:
node = q.popleft()
out.append(node.val)
q.extend(c for c in (node.left, node.right) if c)
return out
print(levels(mirror(T(4, T(2, T(1), T(3)), T(7, T(6), T(9)))))) # -> [4, 7, 2, 9, 6, 3, 1]
print(levels(mirror(T(2, T(1), T(3))))) # -> [2, 3, 1]
print(levels(mirror(None))) # -> []Travou na ideia, e não no código? Árvores binárias explica isso.