Contagem do nível mais profundo
A missão
Problema
Dada a raiz de uma árvore binária, retorne o número de níveis no caminho mais longo da raiz até qualquer folha. Uma árvore só com a raiz conta como um nível, e uma árvore vazia conta como zero.
Exemplos
Input: tree = 3 with children 9 and 20, where 20 has children 15 and 7
Output: 3
Por quê: o caminho 3, 20, 15 cobre três níveis
Input: tree = 1 with a right child 2, whose right child is 3
Output: 3
Por quê: uma árvore totalmente desbalanceada ainda conta cada nível
Input: tree = empty
Output: 0
Por quê: edge case: não há níveis para contar
Dicas
0 / 3
A profundidade de uma árvore é decidida inteiramente pelas suas duas subárvores, que também são árvores. Essa autossimilaridade é a solução inteira.
Defina a resposta de um nó em termos das respostas dos filhos dele e escolha, para o filho ausente, um caso base que faça a conta funcionar.
Para um nó ausente, informe zero níveis. Para qualquer nó real, pergunte a profundidade aos dois filhos, fique com a maior e some um pelo nível que o próprio nó ocupa.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(h)
Restrições
- the tree may be empty
Solução
A profundidade é definida recursivamente: um nó ausente contribui com zero níveis, e um nó presente contribui com um a mais que a mais profunda das suas duas subárvores. Essa única regra trata árvores balanceadas e desbalanceadas da mesma forma, sem nenhum caso especial além do filho vazio. Cada nó é visitado exatamente uma vez. O tempo é O(n), e o espaço é O(h) para a pilha de chamadas (call stack), em que h é a altura da árvore.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def depth(node):
if node is None: return 0 # an absent branch adds no level
# a node sits exactly one level above its deeper subtree
return 1 + max(depth(node.left), depth(node.right))
print(depth(T(3, T(9), T(20, T(15), T(7))))) # -> 3
print(depth(T(1, None, T(2, None, T(3))))) # -> 3
print(depth(None)) # -> 0Travou na ideia, e não no código? Profundidade e balanceamento da árvore explica isso.