Pular para o conteúdo

Profundidade da folha mais rasa

Fácil#bfs#level-order~15 min

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

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

Restrições

  • the tree may be empty

Travou na ideia, e não no código? O básico de árvores explica isso.

Python 3Ctrl+Enter executa