递归回溯时机？

Question

老师，问一下113路径总和和129根节点到叶节点数字之和这两个题，基本都是一样的模式，为什么113的list需要回溯而129的count值不需要回溯呢，是因为int类型和list类型的区别嘛

113

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root==null){
            return res;
        }
        dfs(root,targetSum,new ArrayList<>());
        return res;
    }
    public void dfs(TreeNode root, int targetSum,List<Integer> list){
        if (root==null){
            return;
        }
        list.add(root.val);
        if (root.val==targetSum&&root.left==null&&root.right==null){
            res.add(new ArrayList<>(list));
            list.remove(list.size()-1);
            return;
        }
        if (root.left!=null){
            dfs(root.left,targetSum-root.val,list);
        }
        if (root.right!=null){
            dfs(root.right,targetSum-root.val,list);
        }
        list.remove(list.size()-1);
        return;
    }
}

129
class Solution {
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        if (root==null){
            return 0;
        }
        dfs(root,0);
        return sum;
    }
    public void dfs(TreeNode root,int count){
        if (root==null){
            return;
        }
        count=count *10 + root.val;
        if (root.left==null&&root.right==null){
            sum+=count;
            return;
        }
        dfs(root.left,count);
        dfs(root.right,count);
        return;
    }
}

Answer 1

liuyubobobo 2022-10-02 01:19:41

对的，是 list 和 int 的区别。list 是对象，是引用；int 是基本数据类型，是值。

当你改变 list 的时候，改变的是引用。所以返回到上一层递归的时候，list 也跟着变了；

当你改变 count 的时候，改变的是当前递归函数中的 count 值，不影响上一层递归中的 count。

继续加油！：）