Verificar se a árvore é balanceada
A missão
Problema
Um índice de busca guarda as chaves em uma árvore binária e a reconstrói sempre que ela fica desbalanceada. Uma árvore é balanceada em altura quando, em todo nó, as alturas das subárvores esquerda e direita diferem em no máximo 1. Dada a raiz de uma árvore binária, retorne True se ela for balanceada em altura. A árvore tem até 5.000 nós, então recalcular a altura a partir de cada nó é desperdício.
Exemplos
Input: tree = 3, left 9, right 20 (children 15 and 7)
Output: True
Input: tree = 1, left 2 (left child 3 with children 4 and 4, right child 3), right 2
Output: False
Por quê: na raiz, o lado esquerdo tem 3 níveis de profundidade e o direito, só 1
Input: tree = empty
Output: True
Por quê: edge case: uma árvore vazia não tem nada fora de equilíbrio
Dicas
0 / 3
Chamar uma função de altura a partir de cada nó visita os nós de baixo de novo e de novo, o que é quadrático em uma árvore alta.
Um nó precisa das alturas dos filhos de qualquer jeito para se testar, e a própria altura dele é um a mais que a maior delas. Um único percurso de baixo para cima consegue calcular as duas coisas.
Retorne a altura de cada subárvore a partir de um percurso em pós-ordem, ou -1 como sinal de que alguma subárvore abaixo já está desbalanceada. Repasse o -1 direto para cima assim que o vir.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(h)
Restrições
- n ≤ 5000 nodes
Solução
Um único percurso em pós-ordem (postorder) retorna a altura de cada subárvore ao pai, então cada nó consegue verificar o próprio balanceamento a partir de números que os filhos já calcularam. Quando um nó descobre que as duas alturas diferem em mais de um, ele retorna -1 em vez de uma altura, e todo ancestral repassa esse -1 direto para cima sem fazer mais trabalho. A árvore é balanceada exatamente quando a raiz não retorna -1. Todo nó é visitado uma vez, então o tempo é O(n), e o espaço é O(h) para a recursão.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_balanced(root):
def height(node): # height, or -1 if unbalanced below
if node is None:
return 0
lh = height(node.left)
if lh == -1:
return -1
rh = height(node.right)
if rh == -1 or abs(lh - rh) > 1:
return -1
return 1 + max(lh, rh)
return height(root) != -1
print(is_balanced(T(3, T(9), T(20, T(15), T(7))))) # -> True
print(is_balanced(T(1, T(2, T(3, T(4), T(4)), T(3)), T(2)))) # -> False
print(is_balanced(None)) # -> TrueTravou na ideia, e não no código? Profundidade e balanceamento da árvore explica isso.