Path Sum

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

O(n) : cada nodo se visita como máximo una vez, 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 en forma de marcos de llamada o de entradas en tu propia pila.

FácilRecorrido de árboles

+10

Recibes 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 cuyas dos posiciones de hijo 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 de la raíz a una hoja
Devuelveboolean: verdadero si algún camino desde la raíz hasta una hoja suma targetSum; falso en caso contrario

Restricciones

1 ≤ tree.length ≤ 32767
Cada tree[i] es -1 o un valor que cumple 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 las hojas suman 14, 10 y 16, y ninguno de ellos es 12.

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

Para ir más allá

¿Puedes contar las rutas que suman targetSum si una ruta puede comenzar en cualquier nodo y terminar en cualquier nodo situado debajo de él?

Pistas

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

0 de 3 abiertas

Solución

Solo cuentan las rutas completas, desde la raíz hasta una hoja. La suma acumulada puede alcanzar targetSum en un nodo que todavía tiene hijos, y eso no cuenta. Así que lleva la suma de la ruta hasta cada nodo, como parámetro o en una pila, y compárala con el objetivo solo en las hojas.

Recursión sobre la suma restante

Intuición

Un camino cuya suma es targetSum empieza con el valor de la raíz, así que el resto, 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 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. En el segundo, el 9 ya deja 0, pero tiene un hijo, así que la búsqueda continúa. Cada nodo se visita una vez, tiempo O(n), y la pila de llamadas contiene un marco por nivel, como máximo 15.

Algoritmo

Escribe walk(i, remaining) y resta tree[i] a remaining.
Si ambos espacios de hijos de i están vacíos (í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 conserva un número por llamada. Guárdalo tú en su lugar, en una pila junto a cada nodo: la suma del camino desde la raíz hasta ese nodo. Empieza con (0, tree[0]); cada hijo recibe la suma de su padre más su propio valor. Saca un par de la pila. Si el nodo es una hoja con suma targetSum, ya terminaste; de lo contrario, apila sus hijos reales.

Cada nodo real se apila una vez: tiempo O(n), y la pila guarda aproximadamente un hermano en espera por nivel: O(h). El mismo bucle funciona en un árbol profundo basado en punteros, donde la recursión podría quedarse sin espacio en la pila.

Algoritmo

Apila (0, tree[0]) en una pila.
Desapila un par (i, total) y mira 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

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.
Permitir que un espacio vacío para un hijo termine un camino. Después, el 9 del segundo ejemplo termina un camino a través de su espacio izquierdo vacío.
Olvidarse de la raíz por sí sola. Un nodo único es una hoja, así que [4] con el objetivo 4 es true, y también lo es [0] con el objetivo 0.
Leer más allá del final del arreglo. Una hoja cerca del final puede tener índices de hijos que superen la última entrada.
Confundir el desplazamiento en Lua y R. Mantén los índices de los nodos en base 0 para 2*i+1 y lee tree[i + 1].

Preguntas frecuentes3

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

O(n): cada nodo se visita como máximo una vez, 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 en forma de marcos de llamada o de entradas en tu propia pila.

¿Se puede resolver Path Sum con BFS?

Sí. Coloca pares de un nodo y la suma de su ruta en una cola en lugar de una pila, y comprueba cada hoja cuando sale. El tiempo sigue siendo O(n), pero la cola puede contener un nivel completo, 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 cuya suma sea igual al 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 subir. El recorrido sigue siendo el mismo. Copiar las rutas puede costar más que el recorrido cuando coinciden muchas hojas.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

true