Trova percorsi in un albero di ricerca binario sommando a un valore di destinazione

Question

Dato un albero di ricerca binario e un valore di destinazione, trova tutti i percorsi (se ne esiste più di uno) che si sommano al valore di destinazione. Può essere qualsiasi percorso nell'albero. Non deve essere dalla radice.

Ad esempio, nel seguente albero binario di ricerca:

2 
/\ 
1 3 

quando la somma dovrebbe essere di 6, il percorso 1 -> 2 -> 3 deve essere stampato.

Answer 1

Attraversare l'albero dalla radice e eseguire una raccolta post-ordine di tutte le somme dei percorsi. Utilizzare una tabella hash per archiviare i possibili percorsi radicati in un nodo e andare solo verso il basso. Possiamo costruire tutti i percorsi che attraversano un nodo da se stesso e dai percorsi dei suoi figli.

Ecco il codice psuedo che implementa quanto sopra, ma memorizza solo le somme e non i percorsi effettivi. Per i percorsi stessi, è necessario memorizzare il nodo finale nella tabella hash (sappiamo dove inizia e c'è solo un percorso tra due nodi in un albero).

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 

Questo non usa il fatto che l'albero è un albero di ricerca, in modo che possa essere applicato a qualsiasi albero binario.

Per alberi di grandi dimensioni, la dimensione della tabella di estensione aumenterà di mano. Se ci sono solo valori positivi, potrebbe essere più efficiente utilizzare una matrice indicizzata dalla somma.

Answer 2

La mia risposta è O(n^2), ma credo che sia accurata e prende un leggermente diverso da approccio e sembra più facile da implementare.

Si supponga che il valore memorizzato nel nodo i sia denotato da VALUE[i]. La mia idea è di memorizzare su ogni nodo la somma dei valori sul percorso da root a quel nodo. Quindi per ogni nodo i, SUM[i] è la somma del percorso da root al nodo i.

Quindi, per ogni coppia di nodi (i,j), trovare il loro antenato comune k. Se SUM(i)+SUM(j)-SUM(k) = TARGET_SUM, hai trovato una risposta.

Questo è O(n^2) poiché stiamo eseguendo il ciclo su tutte le coppie di nodi. Anche se, mi piacerebbe poter capire un modo migliore di scegliere solo tutte le coppie.

Potremmo ottimizzarlo un po 'scartando sottotasti in cui il value del nodo radicato nella sottostruttura è maggiore di TARGET_SUM. Eventuali ulteriori ottimizzazioni sono i benvenuti :)

psuedocodarlo:

# 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) 

Funzione common_ancestor è un problema abbastanza standard per un albero binario di ricerca. Psuedocode (dalla memoria, si spera non ci siano errori!):

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

vecchia questione, ma ecco il mio pugnalata a lui - dovrebbe essere O (n) al momento in cui la vostra visita ogni nodo una sola volta:

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); 
    } 

E la classe del nodo:

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

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