Verificação de simetria espelhada
A missão
Problema
Decida se uma árvore binária é a imagem espelhada de si mesma, como se uma linha vertical passasse pela raiz. Tanto o formato quanto os valores precisam coincidir dos dois lados dessa linha. Uma árvore vazia conta como simétrica.
Exemplos
Input: tree = 1, left 2 with children 3 and 4, right 2 with children 4 and 3
Output: True
Por quê: a subárvore direita é a subárvore esquerda lida de trás para frente
Input: tree = 1, left 2 with right child 3, right 2 with right child 3
Output: False
Por quê: os dois 3 ficam pendurados do mesmo lado, então o formato não é espelhado
Input: tree = empty
Output: True
Por quê: edge case: o vazio é trivialmente simétrico
Dicas
0 / 3
Simetria não é uma propriedade de um nó por vez; é uma propriedade de pares de nós que ficam frente a frente, cada um de um lado da linha do meio.
Faça uma pergunta diferente da óbvia: em vez de “esta árvore é simétrica?”, pergunte “estas duas subárvores são imagens espelhadas uma da outra?”.
Compare as subárvores esquerda e direita da raiz como um par. Duas subárvores se espelham quando ambas estão ausentes, ou quando ambas estão presentes com valores iguais e o filho esquerdo de uma espelha o filho direito da outra, nos dois sentidos.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(h)
Restrições
- the tree may be empty
Solução
A recursão natural é sobre pares, e não sobre nós isolados: duas subárvores se espelham quando as raízes coincidem e os filhos se espelham cruzados, externo contra externo e interno contra interno. O caso base precisa distinguir ambos ausentes, que é uma correspondência, de apenas um ausente, que é uma divergência de formato, e uma comparação de identidade cobre os dois casos de uma vez. Cada nó é visitado uma vez. O tempo é O(n), e o espaço é O(h) para a pilha de chamadas (call stack).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_symmetric(root):
def mirrors(a, b):
if a is None or b is None:
return a is b # true only when both are absent
# outer child against outer child, inner child against inner child
return (a.val == b.val and mirrors(a.left, b.right)
and mirrors(a.right, b.left))
return root is None or mirrors(root.left, root.right)
print(is_symmetric(T(1, T(2, T(3), T(4)), T(2, T(4), T(3))))) # -> True
print(is_symmetric(T(1, T(2, None, T(3)), T(2, None, T(3))))) # -> False
print(is_symmetric(None)) # -> TrueTravou na ideia, e não no código? Árvores binárias explica isso.