Wann ist Backtracking notwendig?

Question

Zum Beispiel die folgenden zwei Fragen über DFS ein binärer Baum, warum die erste Rückverfolgung benötigt (löschen Sie das letzte Element in der Arbeitsmenge jedes Mal, wenn Sie einen Blattknoten treffen), und die andere nicht? Sie haben beide gefragt, ob alle Pfade die Anforderung erfüllen und nicht versuchen herauszufinden, ob ein Pfad existiert oder nicht, da der Pfad bereits erreicht ist, wenn ein Blatt getroffen wird, um einen anderen möglichen Pfad zu formatieren, sollten wir nicht zurück zu verfolgen der letzte Knoten, den wir besuchen?

https://leetcode.com/problems/path-sum-ii/

https://leetcode.com/problems/binary-tree-paths/

Antwort für die erste Frage:

public List<List<Integer>> pathSum(TreeNode root, int sum) { 
    List<List<Integer>> finalResult=new ArrayList<List<Integer>>(); 
    List<Integer> tempResult = new ArrayList<Integer>(); 
    pathSumHelper(root,sum,tempResult,finalResult); 
    return finalResult; 
} 
public void pathSumHelper(TreeNode node, int sum, List <Integer> tempResult, List<List<Integer>> finalResult){ 
    if(node == null) return; 
    sum -= node.val; 
    if(node.left == null && node.right == null){ 
     if(sum == 0){ 
      tempResult.add(node.val); 
      finalResult.add(new ArrayList<Integer>(tempResult)); 
      tempResult.remove(tempResult.size() -1); 
     } 
    return; 
    } 
    tempResult.add(node.val); 
    pathSumHelper(node.left, sum, tempResult, finalResult); 
    pathSumHelper(node.right, sum, tempResult, finalResult); 
    tempResult.remove(tempResult.size() -1); 
} 

Antwort für die zweite Frage:

public List<String> binaryTreePaths(TreeNode root) { 
    List<String> finalResult = new ArrayList<String>(); 
    String tempResult = ""; 
    findPath(root, tempResult, finalResult); 
    return finalResult; 
} 

public void findPath(TreeNode node, String tempResult, List<String> finalResult){ 
    if(node == null){ 
     return; 
    } 
    if(node.left == null && node.right == null){ 
     tempResult += String.valueOf(node.val);   
     finalResult.add(tempResult); 
     // why no delete last integer added in tempResult before return? 
     return; 
    } 
    tempResult += String.valueOf(node.val); 
    findPath(node.left, tempResult+"->", finalResult); 
    findPath(node.right, tempResult+"->", finalResult); 
    // same, why no delete last integer added in tempResult before return?    
} 

Answer 1

Im zweiten Algorithmus, wenn Sie einen rekursiven Anruf Um den Pfad zu finden, verwenden Sie + operator, während tempResult + "->" als Argument übergeben wird. + Operator verursacht eine Verkettung, die ein neues String-Objekt erstellt. Grundsätzlich übergeben Sie auf jeder Rekursionsebene ein neues String-Objekt an die unteren Ebenen und lassen die tempResult-Variable jeder Ebene außerhalb der Reichweite niedrigerer Ebenen.

Folglich haben Sie tatsächlich keinen Zugriff auf das String-Objekt der oberen Rekursionsebenen und selbst wenn Sie zurückverfolgen, würde es nur das String-Objekt aktualisieren, das an diese Rekursionsebene übergeben wurde, und nicht das zu einer höheren Ebene gehörende tempResult Das war nie zufällig! Deshalb ist das Zurückverfolgen in der zweiten Lösung nicht notwendig und wird daher nicht durchgeführt.