Pular para o conteúdo

Soma alvo da raiz até a folha

Fácil#dfs#recursion~20 min

A missão

Problema

Dada uma árvore binária e um número alvo, decida se existe algum caminho da raiz até uma folha cujos valores somem exatamente o alvo. Uma folha é um nó sem filhos, então um caminho sempre precisa terminar na base da árvore. Os valores podem ser negativos.

Exemplos

Input:  tree = 5, left 4 with left child 11 having children 7 and 2,
        right 8 with children 13 and 4; target = 22
Output: True
Por quê: o caminho 5, 4, 11, 2 soma 22
Input:  tree = 1 with a single left child 2; target = 1
Output: False
Por quê: a raiz não é uma folha, então o caminho não pode parar nela
Input:  tree = empty; target = 0
Output: False
Por quê: edge case: uma árvore vazia não tem nenhum caminho da raiz até uma folha

Dicas

0 / 3

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

Restrições

  • values may be negative
  • a path must end at a leaf

Travou na ideia, e não no código? Variações de soma de caminho explica isso.

Python 3Ctrl+Enter executa