什么时候需要回溯？

Question

比如下面两个关于二叉树DFS的问题，为什么第一个需要回溯（每次碰到叶节点就删除工作集中的最后一个元素），另一个不需要？他们都要求所有的路径都满足要求，而不是试图寻找路径是否存在，因为当碰到叶子时路径已经走到尽头，为了格式化其他可能的路径我们是否应该回溯到我们访问的最后一个节点？

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

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

第一个问题的答案：

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

第二题答案：

 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

在第二种算法中，当您对 findPath 进行递归调用时，您使用的是 + 运算符，同时传递 tempResult + "->" 作为参数。 + 运算符导致创建新的 String 对象的连接。基本上在每个递归级别，您将一个新的 String 对象传递到较低级别，并将每个级别的 tempResult 变量留在较低级别的范围之外。

因此，您实际上无权访问上层递归的 String 对象，即使您回溯，它也只会更新传递给该递归层的 String 对象而不是属于上层的 tempResult，它从来没有机会开始！这就是为什么在第二个解决方案中不需要回溯的原因，因此没有完成。

什么时候需要回溯？

When backtracking is necessary?

java

algorithm

recursion

binary-tree

backtracking