java - 什么时候需要回溯？

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，这是从来没有机会开始的!这就是为什么在第二种解决方案中不需要回溯的原因，因此没有进行。