Maximum Depth of Binary Tree
Você recebe uma árvore binária armazenada no array tree em ordem por níveis. A raiz fica no índice 0, os filhos do nó no índice i ficam em 2*i+1 (à esquerda) e 2*i+2 (à direita), -1 marca uma posição vazia, e o array pode terminar com entradas extras -1. Retorne a profundidade máxima da árvore: o número de nós no caminho mais longo da raiz até uma folha.
Função
- treeinteger-array
- a árvore binária em ordem por nível, com -1 para uma posição vazia
- Retornainteger
- o número de nós no caminho mais longo da raiz até uma folha
Restrições
1 ≤ tree.length ≤ 32767- Cada
tree[i]é-1ou um valor com0 ≤ tree[i] ≤ 1000. tree[0]nunca é-1, então a árvore tem pelo menos um nó.- O array pode terminar com entradas
-1extras após o último nó. - Ambos os filhos de um espaço vazio também estão vazios, e a profundidade é no máximo
14.
Exemplos
- Entrada
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- Saída
- 4
- Explicação
- O caminho mais longo é
5,8,3,6(índices0,1,4,9), que contém 4 nós. O caminho que passa por1termina após 2 nós.
- Entrada
- tree = [7, -1, -1]
- Saída
- 1
- Explicação
- As duas entradas
-1são os espaços vazios para filhos do nó raiz. O nó raiz sozinho forma um caminho de um nó, portanto a profundidade é1, não0.
- Entrada
- tree = [2, -1, 9, -1, -1, -1, 4]
- Saída
- 3
- Explicação
- A raiz
2não tem filho à esquerda. Seu filho à direita9, no índice2, tem o4no índice6como filho à direita, um caminho de 3 nós.
Para ir além
Como você retornaria os valores de um caminho mais longo da raiz até uma folha, além de seu comprimento? Se vários caminhos tiverem o mesmo comprimento, qual deles você retornaria?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Pense na raiz. Se você soubesse a profundidade da subárvore esquerda e a profundidade da subárvore direita, qual seria a profundidade da árvore inteira?
É
1para a raiz mais a maior das profundidades das duas subárvores, e um espaço vazio tem profundidade0. A mesma regra vale em todos os nós, então uma travessia que saiba a profundidade de cada nó pode encontrar a resposta.Mantenha uma pilha de pares, um índice de nó e sua profundidade, começando com a raiz na profundidade 1. Remova um par da pilha, registre a maior profundidade encontrada e adicione cada filho nos índices
2*i+1e2*i+2que esteja dentro do array e não seja-1, com a profundidade acrescida de um.
Solução
A profundidade é determinada pelo ramo mais longo, e você não pode saber qual ramo é esse sem visitar todos os nós. Portanto, você precisa de uma travessia completa que saiba a profundidade em cada nó. A recursão, uma busca em largura por níveis e uma busca em profundidade com sua própria pilha fazem isso em uma única passagem.
Recursão nas duas subárvores
Intuição
Um espaço filho é real quando seu índice está dentro do array e seu valor não é -1. O caminho mais profundo através de um nó desce até sua subárvore mais profunda, então a profundidade no índice i é 1 para o nó mais o maior entre as profundidades em 2*i+1 e 2*i+2. Um espaço vazio tem profundidade 0, o que encerra a recursão. Uma folha recebe 1 + max(0, 0) = 1, e os valores sobem de volta até a raiz.
Cada nó é visitado uma vez. A pilha de chamadas contém um quadro por nível do caminho atual, O(h), no máximo 14 aqui.
Algoritmo
- Escreva
depth(i): seiestiver além do fim do array outree[i]for-1, retorne0. - Caso contrário, retorne
1 + max(depth(2*i+1), depth(2*i+2)). - Retorne
depth(0).
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)Busca em largura, nível por nível
Intuição
A profundidade máxima é o número de níveis, então você pode contar os níveis em vez de seguir os caminhos. Uma fila visita os nós na ordem dos níveis. Antes de cada lote, leia o tamanho da fila: esses nós formam exatamente um nível, porque os filhos que você adiciona durante o lote entram atrás deles. Cada lote aumenta a profundidade em 1. No primeiro exemplo, os lotes são [5], [8, 1], [3] e [6], então a resposta é 4.
A fila contém um nível por vez, O(w) para o nível mais largo. Em uma árvore completa com profundidade 14, isso corresponde a 8192 dos 16383 nós.
Algoritmo
- Coloque o índice raiz
0em uma fila e definadepth = 0. - Enquanto a fila não estiver vazia, adicione
1adepthe leia o tamanho da fila. - Retire essa quantidade de índices. Para cada um, coloque na fila os índices dos filhos
2*i+1e2*i+2que estejam dentro do array e não sejam-1. - Quando a fila estiver vazia, retorne
depth.
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depthBusca em profundidade com uma pilha explícita
Intuição
Mantenha sua própria pilha de pares, com o índice de um nó e sua profundidade, já que nada mais registra a profundidade de um nó. Comece com (0, 1), a raiz na profundidade 1. Cada nó é empilhado uma vez, levando o comprimento do caminho que chega até ele, então a maior profundidade que você desempilhar é a resposta. No primeiro exemplo, o 6 é empilhado como (9, 4).
A pilha contém cerca de um irmão pendente por nível, O(h), sem pilha de chamadas que possa estourar. O mesmo código funciona em uma árvore baseada em ponteiros de qualquer profundidade.
Algoritmo
- Empilhe
(0, 1)e definabest = 0. - Remova um par
(i, depth)da pilha e definabestcomo o maior entrebestedepth. - Para cada índice de filho
2*i+1e2*i+2que esteja dentro dos limites do array e não seja-1, empilhe-o comdepth + 1. - Repita até que a pilha esteja vazia e, em seguida, retorne
best.
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
Armadilhas e casos extremos
- Contar arestas em vez de nós.
[7, -1, -1]tem profundidade1, não0. - Ignorar a verificação dos limites. No primeiro exemplo, o
6no índice 9 tem índices filhos 19 e 20, além do fim do array. Verifiquechild < nantes de lertree[child]. - Calcular a profundidade com base no comprimento do array. Entradas
-1no final chegam a um nível sem nó:[7, -1, -1]tem comprimento 3, mas profundidade 1. - Ler o tamanho da fila dentro do loop do lote. Os filhos adicionados durante o lote o alteram, então salve-o primeiro.
- Confundir o deslocamento em Lua e R, onde os arrays começam em 1. Mantenha os índices dos nós baseados em 0 para
2*i+1e leiatree[i + 1].
Perguntas frequentes3
Qual é a complexidade de tempo de Maximum Depth of Binary Tree?
Cada abordagem visita cada nó uma vez, então o tempo é O(n). As versões em profundidade usam O(h) de espaço extra para o caminho atual, em que h é a profundidade. A versão em largura usa O(w) para o nível mais largo, cerca de metade dos nós em uma árvore completa.
Você deve usar DFS ou BFS para encontrar a profundidade máxima de uma árvore binária?
Ambas têm complexidade de tempo O(n). A busca em profundidade é mais curta de escrever e usa memória proporcional à profundidade, o que é adequado para árvores largas e rasas. A busca em largura conta os níveis diretamente e usa memória proporcional ao nível mais largo, o que é adequado para árvores profundas e estreitas. Para encontrar a profundidade mínima, a busca em largura leva vantagem porque pode parar na primeira folha.
Qual é a diferença entre a profundidade e a altura de uma árvore binária?
A profundidade de um nó conta os passos da raiz até ele; a altura conta os passos dele até sua folha mais profunda. A profundidade máxima da árvore é igual à altura da raiz. Este problema conta nós, então um único nó tem profundidade 1; contar arestas resulta em um a menos.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def maxDepth(tree):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Saída Esperada
4