Path Sum leetcode java
2343 ワード
タイトル:
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example:
Given the below binary tree and
return true, as there exist a root-to-leaf path
問題:
ツリーの操作、再帰的な解法です.
1
public
boolean hasPathSum(TreeNode root,
int sum) {
2
if(root ==
null)
3
return
false;
4
5 sum -= root.val;
6
if(root.left ==
null && root.right==
null)
7
return sum == 0;
8
else
9
return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
10 }
非再帰的解法(Reference:http://www.programcreek.com/2013/01/leetcode-path-sum/):
1
public
boolean hasPathSum(TreeNode root,
int sum) {
2
if(root ==
null)
return
false;
3
4 LinkedList nodes =
new LinkedList();
5 LinkedList values =
new LinkedList();
6
7 nodes.add(root);
8 values.add(root.val);
9
10
while(!nodes.isEmpty()){
11 TreeNode curr = nodes.poll();
12
int sumValue = values.poll();
13
14
if(curr.left ==
null && curr.right ==
null && sumValue==sum){
15
return
true;
16 }
17
18
if(curr.left !=
null){
19 nodes.add(curr.left);
20 values.add(sumValue+curr.left.val);
21 }
22
23
if(curr.right !=
null){
24 nodes.add(curr.right);
25 values.add(sumValue+curr.right.val);
26 }
27 }
28
29
return
false;
30 }
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example:
Given the below binary tree and
sum = 22
, 5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path
5->4->11->2
which sum is 22.問題:
ツリーの操作、再帰的な解法です.
1
public
boolean hasPathSum(TreeNode root,
int sum) {
2
if(root ==
null)
3
return
false;
4
5 sum -= root.val;
6
if(root.left ==
null && root.right==
null)
7
return sum == 0;
8
else
9
return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
10 }
非再帰的解法(Reference:http://www.programcreek.com/2013/01/leetcode-path-sum/):
1
public
boolean hasPathSum(TreeNode root,
int sum) {
2
if(root ==
null)
return
false;
3
4 LinkedList
new LinkedList
5 LinkedList
new LinkedList
6
7 nodes.add(root);
8 values.add(root.val);
9
10
while(!nodes.isEmpty()){
11 TreeNode curr = nodes.poll();
12
int sumValue = values.poll();
13
14
if(curr.left ==
null && curr.right ==
null && sumValue==sum){
15
return
true;
16 }
17
18
if(curr.left !=
null){
19 nodes.add(curr.left);
20 values.add(sumValue+curr.left.val);
21 }
22
23
if(curr.right !=
null){
24 nodes.add(curr.right);
25 values.add(sumValue+curr.right.val);
26 }
27 }
28
29
return
false;
30 }