递归回溯时机?
来源: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。
继续加油!:)
00
相似问题