Suma objetivo de raíz a hoja
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
El árbol divide la pregunta en dos preguntas más pequeñas del mismo tipo, una por cada hijo, y la respuesta es sí cuando cualquiera de ellas dice que sí.
En lugar de sumar los valores a la vuelta, resta cada valor del objetivo mientras bajas, para que un hijo solo vea la cantidad que todavía falta.
Baja desde la raíz llevando la cantidad restante. En una hoja, responde sí exactamente cuando lo que resta es igual al valor de esa hoja. En una rama ausente, responde no, para que un nodo con un solo hijo nunca se confunda con un punto de parada.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(h)
Restricciones
- values may be negative
- a path must end at a leaf
Solución
Llevar la cantidad restante hacia abajo convierte la pregunta en cada nodo en la misma pregunta sobre un árbol más pequeño, así que una sola recursión cubre toda la búsqueda. El caso de la rama ausente tiene que responder no en lugar de comprobar lo que resta; si no, un nodo con un solo hijo se trataría como un punto final válido. Una hoja responde comparando lo que resta con su propio valor, y los dos hijos se combinan con un or de cortocircuito. El tiempo es O(n) en el peor caso y el espacio es O(h) para la pila de llamadas (call stack).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def has_path_sum(node, target):
if node is None:
return False # an absent branch is not a stopping point
rest = target - node.val
if node.left is None and node.right is None:
return rest == 0 # only a leaf may close the path
return has_path_sum(node.left, rest) or has_path_sum(node.right, rest)
print(has_path_sum(T(5, T(4, T(11, T(7), T(2))), T(8, T(13), T(4))), 22)) # -> True
print(has_path_sum(T(1, T(2)), 1)) # -> False
print(has_path_sum(None, 0)) # -> False¿Lo que te frena es la idea y no el código? Variantes de suma de caminos lo explica.