AcWing 47. 二叉树中和为某一值的路径 Java
原题链接
中等
作者:
Shanzhihong
,
2019-07-22 20:40:09
,
所有人可见
,
阅读 2634
直接上代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private static List<List<Integer>> ans = new ArrayList<>();
private static List<Integer> path = new ArrayList<>();
public List<List<Integer>> findPath(TreeNode root, int sum) {
dfs(root, sum);
return ans;
}
public void dfs(TreeNode root, int sum){
if(root == null) return;
path.add(root.val);
sum -= root.val;
if(root.left == null && root.right == null && sum == 0){
//引用调用,需要复制path内容,不然存在ans中的为引用
List <Integer> tmp = new ArrayList <>();
tmp.addAll(path);
ans.add(tmp);
}
dfs(root.left, sum);
dfs(root.right, sum);
path.remove(path.size() - 1);
}
}
神奇,最后一步还原,我用的path.remove((Integer)root.val)然后报错了,用size()-1就对了,可能没考虑到有重复元素的原因
这里是不满足要删除要删除最后一个元素,恢复现场啊
result.addAll(path); //把path中的每一个元素加到result中,result.size()==path.size()
result.add(list); //将path作为一个元素加到result中,则result.size()为1
请问为什么要复制path内容呢?path不是静态变量吗(全局使用)
请问你知道为什么了么,我也没看懂
这里应该是要将path中的值拿出来,放入一个新的集合中,再加入到结果,要不然它们共用一个path,java引用调用,后面的值一旦更改,会影响结果集合中的值。
不明觉厉
path.remove(path.size() - 1);为什么要减1鸭~
最后一个元素的下标
这里,我的看法是dfs执行到这一步表示此路不通(你看看原题目一直顺着左边走到9,sum不为0,path加进去没有用,所以9这个节点不行退回到12,那9这个节点在第一步path.add(root.val)已经加进去,所以我们要把退出来,就把最后一个元素即9弹出),也就是y总说的还原现场
赞