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 nos índices 2*i+1 (esquerdo) e 2*i+2 (direito), -1 indica 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
- árvore binária em ordem por níveis, 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 vetor pode terminar com entradas extras
-1apó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 por1para 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 da raiz. A raiz sozinha é um caminho de um nó, então 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 à direita9no índice2tem o4no índice6como filho à direita, um caminho de 3 nós.
+13 testes ocultos ao enviar
Para ir além
Como você retornaria os valores de um caminho mais longo da raiz até uma folha, e não apenas seu comprimento? Se vários caminhos empatarem, qual deles você retornaria e como especificaria isso no contrato?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Pense na raiz. Se você soubesse a profundidade de sua subárvore esquerda e a profundidade de sua 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 para cada nó, 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 estejam dentro dos limites do array e não sejam-1, com a profundidade acrescida de um.
Solução
A profundidade é definida pelo ramo mais longo, e você não consegue saber qual ramo é esse sem examinar todos os nós. Portanto, a tarefa é percorrer a árvore inteira, sabendo a profundidade em cada nó. A recursão, uma busca em largura nível por nível e uma busca em profundidade com uma pilha própria fazem isso em uma única passagem; elas diferem na forma como acompanham onde estão.
Recursão nas duas subárvores
Intuição
Primeiro, como percorrer o array. O nó no índice i tem o filho esquerdo no índice 2*i+1 e o filho direito no índice 2*i+2. Um filho só existe se seu índice estiver dentro do array e o valor nesse índice não for -1. Em [5, 8, 1, -1, 3, -1, -1, -1, -1, 6], a raiz 5 tem filhos nos índices 1 e 2, o 8 no índice 1 tem um espaço vazio à esquerda no índice 3 e o 3 no índice 4 à direita, e esse 3 tem o 6 no índice 9 abaixo dele.
Agora, a ideia. O caminho mais profundo que passa por um nó segue pelo mais profundo dos seus dois subárvores. Portanto, a profundidade da subárvore no índice i é 1 para o próprio nó mais a maior das profundidades nos índices 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, então o tempo é O(n). A pilha de chamadas contém um quadro por nível do caminho atual, O(h), em que h é a profundidade, no máximo 14 aqui. Esse limite é o que torna a recursão segura neste problema. Em uma árvore baseada em ponteiros com formato de uma longa cadeia, o mesmo código atingiria o limite de recursão, que é de 1000 quadros em Python.
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 na árvore, 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: comece com a raiz e, sempre que retirar um nó, adicione seus filhos reais ao final.
Para contar os níveis, processe a fila em lotes. Antes de cada lote, verifique quantos nós a fila contém. Esses são exatamente os nós de um nível, porque os filhos que você adiciona durante o lote ficam atrás deles. Retire essa quantidade de nós, enfileire seus filhos e adicione 1 à profundidade. Quando a fila estiver vazia, a profundidade será o número de lotes. No primeiro exemplo, os lotes são [5], [8, 1], [3] e [6], então a resposta é 4.
Cada nó entra e sai da fila uma vez, tempo O(n). A fila contém um nível por vez, espaço O(w) para o nível mais largo w. Em uma árvore completa, o nível inferior contém cerca de metade dos nós: 8192 dos 16383 na profundidade 14.
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
Você pode percorrer caminhos, como a recursão faz, sem realizar nenhuma chamada recursiva. Mantenha sua própria pilha e armazene cada nó junto com sua profundidade, já que nada mais se lembra de quão abaixo ele está. Comece com o par (0, 1): a raiz, na profundidade 1.
Retire um par da pilha, compare sua profundidade com a maior vista até então e adicione cada filho existente com depth + 1. Cada nó da árvore é adicionado exatamente uma vez, carregando o comprimento do caminho que chega até ele, então a maior profundidade que você retirar da pilha será a resposta. No primeiro exemplo, o 6 no índice 9 é adicionado como (9, 4), e nenhum par vai mais fundo.
O tempo é O(n). A pilha contém os irmãos pendentes ao longo do caminho atual, no máximo cerca de um por nível, então o espaço é O(h), igual ao da recursão, mas sem uma pilha de chamadas que possa transbordar. Esta é a versão indicada quando uma árvore pode ser profunda, e ela se aplica sem alterações a árvores baseadas em ponteiros.
Algoritmo
- Empilhe
(0, 1)e definabest = 0. - Retire um par
(i, depth)da pilha e definabestcomo o maior entrebestedepth. - Para cada índice de filho
2*i+1e2*i+2que esteja dentro do array e não seja-1, empilhe-o comdepth + 1. - Repita até que a pilha fique 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
A maioria das respostas incorretas para este problema está errada por uma unidade ou resulta de tratar um espaço vazio como um nó.
- Contar arestas em vez de nós. Um único nó tem profundidade
1aqui; retornar0para ele, ou3para um caminho de 4 nós, é ficar uma unidade abaixo. - Ignorar a verificação dos limites. Uma folha próxima ao fim do array pode ter índices de filhos além de sua última posição, porque o array pode terminar logo após o último nó. Verifique
child < nantes de lertree[child]. - Deduzir a profundidade pelo tamanho do array. O array pode conter entradas extras
-1no final, então seu tamanho pode corresponder a um nível mais profundo do que o de qualquer nó real. - Tratar
-1como um valor. Ele marca um nó ausente, portanto não deve ser colocado na pilha ou na fila, nem contado. - Supor que a árvore é balanceada. A resposta depende do ramo mais longo, como em uma cadeia de 14 nós à esquerda, na qual todos os espaços à direita estão vazios.
- Ler o tamanho da fila dentro do loop na versão de busca em largura. O tamanho muda à medida que os filhos são adicionados, então salve-o antes de o processamento do lote começar.
- Confundir o deslocamento em Lua e R, onde os arrays começam em 1. Mantenha os índices dos nós baseados em 0 para a aritmética
2*i+1e leiatree[i + 1].
Perguntas frequentes4
Qual é a complexidade de tempo da profundidade máxima de uma árvore binária?
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 que está sendo explorado, onde h é a profundidade. A versão em largura usa O(w) para o nível mais amplo, que pode conter 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 fornecem a resposta correta em 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 a profundidade mínima, a BFS leva vantagem, pois pode parar na primeira folha que encontrar.
Como encontrar a profundidade máxima de uma árvore binária sem recursão?
Use uma pilha explícita de pares: um nó e sua profundidade. Comece com a raiz na profundidade 1, remova um par da pilha, registre sua profundidade e adicione cada filho com a profundidade acrescida de um. A maior profundidade removida da pilha é a resposta. Uma fila processada nível por nível também funciona, contando um para cada nível.
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, e a altura de um nó conta os passos dele até sua folha mais profunda. A profundidade máxima da árvore e a altura da raiz são o mesmo número. Este problema conta nós, portanto um único nó tem profundidade 1; alguns livros contam arestas, o que resulta em um a menos.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def maxDepth(tree):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Esperado
4