Buscar rutas en un árbol de búsqueda binaria sumando a un valor objetivo

Question

Dado un árbol de búsqueda binaria y un valor objetivo, encuentre todas las rutas (si hay más de una) que se suman al valor objetivo. Puede ser cualquier camino en el árbol. No tiene que ser desde la raíz.

Por ejemplo, en el siguiente árbol de búsqueda binaria:

2 
/\ 
1 3 

cuando la suma debe ser de 6, el camino 1 -> 2 -> 3 se debe imprimir.

Answer 1

Atraviese el árbol desde la raíz y realice una recopilación posterior al pedido de todas las sumas de ruta. Use una tabla hash para almacenar las posibles rutas enraizadas en un nodo y solo hacia abajo. Podemos construir todos los caminos pasando por un nodo desde él mismo y las rutas de sus hijos.

Aquí está el código psuedo que implementa lo anterior, pero almacena solo las sumas y no las rutas reales. Para las rutas en sí, debe almacenar el nodo final en la tabla hash (sabemos dónde comienza, y solo hay una ruta entre dos nodos en un árbol).

function findsum(tree, target) 
    # Traverse the children 
    if tree->left 
    findsum(tree.left, target) 
    if tree->right 
    findsum(tree.right, target) 

    # Single node forms a valid path 
    tree.sums = {tree.value} 

    # Add this node to sums of children 
    if tree.left 
    for left_sum in tree.left.sums 
     tree.sums.add(left_sum + tree.value) 
    if tree.right 
    for right_sum in tree.right.sums 
     tree.sums.add(right_sum + tree.value) 

    # Have we formed the sum? 
    if target in tree.sums 
    we have a path 

    # Can we form the sum going through this node and both children? 
    if tree.left and tree.right 
    for left_sum in tree.left.sums 
     if target - left_sum in tree.right.sums 
     we have a path 

    # We no longer need children sums, free their memory 
    if tree.left 
    delete tree.left.sums 
    if tree.right 
    delete tree.right.sums 

Esto no utiliza el hecho de que el árbol es un árbol de búsqueda, por lo que se puede aplicar a cualquier árbol binario.

Para árboles grandes, el tamaño de la tabla hash crecerá de las manos. Si solo hay valores positivos, podría ser más eficiente usar una matriz indexada por la suma.

Answer 2

Mi respuesta es O(n^2), pero creo que es precisa, y toma un ligeramente enfoque diferente y parece más fácil de implementar.

Suponga que el valor almacenado en el nodo i se denota por VALUE[i]. Mi idea es almacenar en cada nodo la suma de los valores en la ruta desde root a ese nodo. Por lo tanto, para cada nodo i, SUM[i] es la suma de la ruta de root al nodo i.

Luego, para cada par de nodos (i,j), busque su ancestro común k. Si SUM(i)+SUM(j)-SUM(k) = TARGET_SUM, ha encontrado una respuesta.

Esto es O(n^2) ya que estamos haciendo un bucle sobre todos los pares de nodos. Aunque, desearía poder encontrar una mejor manera que simplemente escoger todas las parejas.

Podríamos optimizarlo un poco descartando subárboles donde el value del nodo enraizado en el subárbol es mayor que TARGET_SUM. Optimizaciones adicionales son bienvenidos :)

psuedocode:

# Skipping code for storing sum of values from root to each node i in SUM[i] 
for i in nodes: 
    for j in nodes: 
     k = common_ancestor(i,j) 
     if (SUM[i] + SUM[j] - SUM[k] == TARGET_SUM): 
      print_path(i,k,j) 

Función common_ancestor es un problema bastante estándar para un árbol de búsqueda binaria. Psuedocode (de memoria, afortunadamente no hay errores!):

sub common_ancestor (i, j): 
    parent_i = parent(i) 
    # Go up the parent chain until parent's value is out of the range. 
    # That's a red flag. 
    while(VAL[i] <= VAL[parent_i] <= VAL[j]) : 
    last_parent = parent_i 
    parent_i = parent(i) 
    if (parent_i == NULL): # root node 
     break 
return last_parent 

Answer 3

vieja pregunta, pero aquí está mi puñalada en ella - debe ser O (n) tiempo que su visita a cada nodo de una sola vez:

public static List<ArrayList<Integer>> pathSum(Node head, int sum) { 
    List<Integer> currentPath = new ArrayList<Integer>(); 
    List<ArrayList<Integer>> validPaths = new ArrayList<ArrayList<Integer>>(); 

    dfsSum(head, sum, currentPath, validPaths); 

    return validPaths; 
    } 

    public static void dfsSum(Node head, int sum, List<Integer> currentPath, List<ArrayList<Integer>> validPaths) { 
    if (head == null) return; 

    currentPath.add(head.val); 

    if (head.left == null && head.right == null && sum == head.val) { 
     validPaths.add(new ArrayList<Integer>(currentPath)); 
    } 

    dfsSum(head.left, sum - head.val, new ArrayList<Integer>(currentPath), validPaths); 
    dfsSum(head.right, sum - head.val, new ArrayList<Integer>(currentPath), validPaths); 
    } 

Y la clase de nodo:

class Node { 
    public int val; 
    public Node left; 
    public Node right; 

    public Node(int val) { 
     this.val = val; 
    } 
    }