Saltar al contenido

Suma objetivo de raíz a hoja

Fácil#dfs#recursion~20 min

La misión

Problema

Dado un árbol binario y un número objetivo, decide si algún camino desde la raíz hasta una hoja tiene valores que suman exactamente el objetivo. Una hoja es un nodo sin hijos, así que un camino siempre tiene que terminar en la parte inferior del árbol. Los valores pueden ser negativos.

Ejemplos

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é: el camino 5, 4, 11, 2 suma 22
Input:  tree = 1 with a single left child 2; target = 1
Output: False
Por qué: la raíz no es una hoja, así que el camino no puede detenerse ahí
Input:  tree = empty; target = 0
Output: False
Por qué: caso límite: un árbol vacío no tiene ningún camino de la raíz a una hoja

Pistas

0 / 3

Tiempo objetivo
O(n)
Espacio objetivo
O(h)

Restricciones

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

¿Lo que te frena es la idea y no el código? Variantes de suma de caminos lo explica.

Python 3Ctrl+Enter ejecuta