algorithm - operaciones - Encuentre rutas en un árbol de búsqueda binario que sume un valor objetivo

arboles binarios pdf

Question

Dado un árbol de búsqueda binario y un valor objetivo, busque todas las rutas (si existen más de una) que sumen el 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 binario:

  2
 / / 
1   3 

cuando la suma debe ser 6, debe imprimirse el camino 1 -> 2 -> 3 .

Answer 1

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

Supongamos que el valor almacenado en el nodo i se denota mediante VALUE[i] . Mi idea es almacenar en cada nodo la suma de los valores en la ruta desde la root a ese nodo. Entonces, para cada nodo i , SUM[i] es la suma de la ruta desde la root hasta el nodo i .

Luego, para cada par de nodos (i,j) , encuentre 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 repitiendo en todos los pares de nodos. Sin embargo, me gustaría poder encontrar una mejor manera que simplemente eligiendo todos los pares.

Podríamos optimizarlo un poco descartando subárboles donde el value del nodo enraizado en el subárbol es mayor que TARGET_SUM . Cualquier optimización adicional es bienvenida :)

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)

La función common_ancestor es un problema bastante estándar para un árbol de búsqueda binario. Psuedocode (de memoria, ¡esperemos que no haya 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 2

Pregunta antigua, pero aquí está mi intento: debería ser O (n) cuando visite cada nodo 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;
    }
  }

Answer 3

Recorra el árbol desde la raíz y realice una recopilación posterior 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 que atraviesan un nodo desde sí mismo y los caminos 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í mismas, debe almacenar el nodo final en la tabla hash (sabemos dónde empieza, 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á fuera de control. Si solo hay valores positivos, podría ser más eficiente usar una matriz indexada por la suma.