递归回溯时机?

来源:7-5 定义递归问题 Binary Tree Path

不考过程序员不改名字

2022-10-01

老师,问一下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;
    }
}
写回答

1回答

liuyubobobo

2022-10-02

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


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


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


继续加油!:)

0
0

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程