来源Leetcode第113题路径总和II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
1
2
3
4
5
6
7
| 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
|
返回:
递归
在递归返回上一层的时候要删去最后一个加入的节点，这样是否就可以认为是址传递呢？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null)
return ans;
helper(root,sum,new ArrayList<>());
return ans;
}
public void helper(TreeNode root,int sum,List<Integer> ss){
if(root == null || sum < 0)
return;
ss.add(root.val);
sum -= root.val;
if(root.left == null && root.right == null && sum == 0)
ans.add(new ArrayList<>(ss));
if(root.left != null && sum > 0)
helper(root.left,sum,ss);
if(root.right != null && sum > 0)
helper(root.right,sum,ss);
ss.remove(ss.size() - 1);
}
|