Pular para o conteúdo

Verificar se a árvore é balanceada

Fácil#post-order#early-exit~15 min

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

Tempo-alvo
O(n)
Espaço-alvo
O(h)

Restrições

  • n ≤ 5000 nodes

Travou na ideia, e não no código? Profundidade e balanceamento da árvore explica isso.

Python 3Ctrl+Enter executa