Path Sum

+10

Se te proporciona un árbol binario almacenado en el arreglo tree en orden por niveles y un número targetSum. La raíz está en el índice 0, los hijos del nodo en el índice i están en 2*i+1 (izquierdo) y 2*i+2 (derecho), -1 indica una posición vacía y el arreglo puede terminar con entradas -1 adicionales. Devuelve true si algún camino desde la raíz hasta una hoja tiene valores que suman targetSum, y false en caso contrario. Una hoja es un nodo sin hijos: las posiciones de ambos hijos están vacías.

Función

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: el árbol binario en orden por niveles, con -1 para una posición vacía
targetSuminteger: el total que debe alcanzar un camino desde la raíz hasta una hoja
Devuelveboolean: verdadero si alguna ruta de la raíz a una hoja suma targetSum; falso en caso contrario

Restricciones

1 ≤ tree.length ≤ 32767
Cada tree[i] es -1 o un valor con 0 ≤ tree[i] ≤ 1000.
tree[0] nunca es -1, así que el árbol tiene al menos un nodo.
El arreglo puede terminar con entradas -1 adicionales después del último nodo.
Ambos hijos de un espacio vacío también están vacíos, y la profundidad es como máximo 14.
0 ≤ targetSum ≤ 15000

Ejemplos

Entrada: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Salida: true
Explicación: La ruta 3, 9, 2 (índices 0, 1, 4) suma 14, y el 2 en el índice 4 es una hoja.

Entrada: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Salida: false
Explicación: 3 + 9 = 12, pero 9 tiene un hijo, así que ningún camino termina ahí. Los tres caminos de la raíz a una hoja suman 14, 10 y 16, y ninguno de ellos es 12.

Entrada: tree = [4, -1, -1]targetSum = 4
Salida: true
Explicación: Ambos espacios hijos de la raíz están vacíos, así que la raíz es una hoja por sí sola. La ruta que contiene solo 4 suma 4.

+14 pruebas ocultas al enviar

Para ir más allá

¿Puedes contar los caminos que suman targetSum cuando un camino puede comenzar en cualquier nodo y terminar en cualquier nodo debajo de él, y no solo ir de la raíz a una hoja?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La pregunta se refiere a rutas completas, desde la raíz hasta una hoja. Un total acumulado puede alcanzar targetSum a mitad de camino, en un nodo que todavía tiene hijos, y eso no cuenta. Así que llevas la suma de la ruta hasta el momento a cada nodo y la comparas con el objetivo solo en las hojas. La recursión lleva esa suma como parámetro; una pila la lleva junto a cada nodo.

Recursión sobre la suma restante

Intuición

Primero, cómo recorrer el array. El nodo en el índice i tiene su hijo izquierdo en 2*i+1 y su hijo derecho en 2*i+2. Un hijo existe solo si su índice está dentro del array y el valor allí no es -1. En [3, 9, 6, -1, 2, 1, 7], la raíz 3 tiene hijos en los índices 1 y 2, y el 9 en el índice 1 tiene un espacio izquierdo vacío en 3 y el 2 en el índice 4 a su derecha.

Ahora, la idea. Un camino cuya suma es targetSum empieza con el valor de la raíz, así que el resto del camino, que empieza en uno de los hijos de la raíz, debe sumar targetSum menos ese valor. Es la misma pregunta en un árbol más pequeño. Resta el valor de cada nodo al avanzar hacia abajo. En una hoja, el camino termina, así que la respuesta allí es si no queda nada.

En el primer ejemplo, la raíz deja 14 - 3 = 11, el 9 deja 2, y la hoja 2 deja 0: true. En el segundo ejemplo, el 9 ya deja 0, pero tiene un hijo, así que la búsqueda continúa, y su hoja termina en -2. Cada nodo se visita como máximo una vez, tiempo O(n), y la pila de llamadas tiene un marco por nivel, O(h), como máximo 15 marcos aquí (una profundidad de 14 cuenta las aristas debajo de la raíz).

Algoritmo

Escribe walk(i, remaining) y resta tree[i] de remaining.
Si ambas posiciones de los hijos de i están vacías (índice fuera del límite o -1), devuelve si remaining es 0.
De lo contrario, devuelve true si walk en un hijo izquierdo real o en un hijo derecho real devuelve true.
Devuelve walk(0, targetSum).

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

Búsqueda en profundidad con una pila explícita

Intuición

La recursión mantiene un número por llamada: cuánto le falta al objetivo. Puedes guardar tú mismo un número así, en una pila junto a cada nodo, y prescindir de las llamadas. Guarda la suma del camino desde la raíz hasta el nodo, incluido el nodo. Empieza con (0, tree[0]) y asigna a cada hijo la suma de su padre más su propio valor.

Desapila un par. Si el nodo es una hoja y su suma es igual a targetSum, has terminado. De lo contrario, apila sus hijos reales. En el primer ejemplo, el lado derecho sale primero de la pila: las hojas 7 y 1 llevan 16 y 10. Después se desapila (1, 12) para el 9. No es una hoja, así que apila (4, 14), una hoja con la suma correcta.

Cada nodo real se apila una vez, así que el tiempo es O(n), y la búsqueda se detiene en la primera hoja que coincide. La pila contiene los hermanos pendientes a lo largo del camino actual, aproximadamente uno por nivel: espacio O(h). El mismo bucle funciona con un árbol profundo basado en punteros, en el que la recursión podría quedarse sin espacio en la pila.

Algoritmo

Apila (0, tree[0]) en una pila.
Extrae un par (i, total) y examina las posiciones de los hijos 2*i+1 y 2*i+2.
Si ninguno de los hijos es real y total es igual a targetSum, devuelve true.
Apila cada hijo real c como (c, total + tree[c]).
Cuando la pila esté vacía, devuelve false.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

Errores comunes y casos límite

Casi todos los errores en este problema tienen que ver con dónde termina un camino.

Comparar la suma en cada nodo. En el segundo ejemplo, 3 + 9 = 12 coincide en el 9, que tiene un hijo, así que la respuesta es false. Compara solo en las hojas.
Tratar una posición vacía de hijo como el final de un camino. Si walk en una posición vacía devuelve remaining == 0, el 9 del segundo ejemplo cuenta como hoja a través de su posición izquierda vacía. Un nodo es una hoja solo cuando ambas posiciones están vacías.
Olvidarse de la raíz por sí sola. Un nodo único es una hoja, así que [4] con targetSum = 4 da true, y también [0] con targetSum = 0.
Detener la búsqueda cuando el total supera el objetivo. Los valores aquí nunca son negativos, así que eso es seguro en este problema, pero el mismo código da respuestas incorrectas en cuanto un árbol puede contener valores negativos.
Leer más allá del final. Una hoja cerca del final del arreglo puede tener índices de hijo que superen su última entrada, porque el arreglo puede terminar justo después del último nodo. Comprueba el índice antes de leer tree[c].
Confundir el desplazamiento en Lua y R, donde los arreglos empiezan en 1. Mantén los índices de los nodos basados en 0 para la aritmética 2*i+1 y lee tree[i + 1].

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Path Sum?

Cada nodo se visita como máximo una vez, así que el tiempo es O(n), y la búsqueda puede detenerse en la primera hoja que coincida. El espacio adicional es O(h) para la ruta que se está explorando, ya sea como marcos de llamada o como entradas en tu propia pila.

¿Por qué Path Sum solo comprueba la suma en los nodos hoja?

El problema pide un camino desde la raíz hasta una hoja, y un camino que termina en un nodo con hijos no lo es. Comprobarlo en cada nodo devuelve true con demasiada frecuencia, por ejemplo, cuando el valor de la raíz por sí solo es igual al objetivo, pero la raíz tiene un hijo. Un nodo termina un camino solo cuando sus dos posiciones de hijo están vacías.

¿Se puede resolver Path Sum con BFS?

Sí. Pon pares de un nodo y la suma de su ruta en una cola en lugar de una pila, y comprueba cada hoja a medida que sale. El tiempo sigue siendo O(n), pero la cola puede contener un nivel entero, aproximadamente la mitad de los nodos de un árbol completo, mientras que una pila contiene aproximadamente un nodo por nivel.

¿Cómo encuentras todos los caminos que suman el objetivo?

Mantén la lista de nodos de la ruta actual mientras bajas, cópiala en la respuesta en cada hoja cuya suma coincida y elimina el último nodo al volver a subir. El recorrido sigue siendo el mismo; solo aumenta el seguimiento. Copiar las rutas puede costar más que el recorrido en sí cuando coinciden muchas hojas.

Python

def hasPathSum(tree, targetSum):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

Esperado

true