Path Sum II leetcode java
1895 ワード
タイトル:
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example:
Given the below binary tree and
return
public
void pathSumHelper(TreeNode root,
int sum, List sumlist, List
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example:
Given the below binary tree and
sum = 22
, 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
:
path sum, , DFS 。 :
1 public
void pathSumHelper(TreeNode root,
int sum, List
- > pathlist){
2
if(root==
null)
3
return;
4 sumlist.add(root.val);
5 sum = sum-root.val;
6
if(root.left==
null && root.right==
null){
7
if(sum==0){
8 pathlist.add(
new ArrayList
9 }
10 }
else{
11
if(root.left!=
null)
12 pathSumHelper(root.left,sum,sumlist,pathlist);
13
if(root.right!=
null)
14 pathSumHelper(root.right,sum,sumlist,pathlist);
15 }
16 sumlist.remove(sumlist.size()-1);
17 }
18
19
public List
- > pathSum(TreeNode root,
int sum) {
20 List
- > pathlist=
new ArrayList
- >();
21 List
new ArrayList
22 pathSumHelper(root,sum,sumlist,pathlist);
23
return pathlist;
24 }