Profundidade da folha mais rasa
A missão
Problema
Dada a raiz de uma árvore binária, retorne o número de nós no caminho mais curto da raiz até uma folha, em que uma folha é um nó sem filhos. Uma árvore vazia tem profundidade 0. Um nó com apenas um filho não é folha, então um caminho que passa por ele precisa continuar até esse filho.
Exemplos
Input: tree = 6, left 2 (whose left is 1, whose left is 0), right 9
Output: 2
Por quê: 9 é uma folha um passo abaixo da raiz
Input: tree = 1, right 2, whose right is 3
Output: 3
Por quê: 1 e 2 têm um filho cada, então só 3 é folha
Input: tree = empty
Output: 0
Por quê: edge case: não há nós
Dicas
0 / 3
A folha mais rasa pode estar em qualquer lado, mas nunca pode estar mais funda que a primeira folha que você encontra ao explorar a árvore nível a nível.
Explore um nível por vez a partir da raiz, lembrando a profundidade de cada nó, e verifique em cada nó se ele é uma folha.
Rode uma busca em largura com uma fila de pares de nó e profundidade. O primeiro nó retirado que não tem filho esquerdo nem direito dá a resposta, então retorne a profundidade dele na hora. Um nó com apenas um filho não é folha.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(w)
Restrições
- the tree may be empty
Solução
A busca em largura (BFS) retira os nós em ordem de profundidade, então a primeira folha que ela retira é uma folha mais rasa, e a busca pode parar ali. Essa parada antecipada compensa quando uma folha fica perto da raiz de uma árvore grande, caso em que uma busca em profundidade (DFS) ainda visitaria todos os nós. O erro fácil é pegar a menor das duas profundidades das subárvores em um nó com um só filho: o lado ausente reporta 0, e o nó é tratado erroneamente como folha. O tempo é O(n) no pior caso, e o espaço é O(w) para o nível mais largo guardado na fila.
from collections import deque
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def min_depth(root):
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, depth = queue.popleft()
if not node.left and not node.right:
return depth # BFS meets the shallowest leaf first
for child in (node.left, node.right):
if child:
queue.append((child, depth + 1))
print(min_depth(T(6, T(2, T(1, T(0))), T(9)))) # -> 2
print(min_depth(T(1, None, T(2, None, T(3))))) # -> 3
print(min_depth(None)) # -> 0Travou na ideia, e não no código? O básico de árvores explica isso.