-
Notifications
You must be signed in to change notification settings - Fork 17
Expand file tree
/
Copy pathSolution.java
More file actions
56 lines (47 loc) · 1.29 KB
/
Solution.java
File metadata and controls
56 lines (47 loc) · 1.29 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package PathSum;
import commons.datastructures.TreeNode;
/**
* User: Danyang
* Date: 1/19/2015
* Time: 19:33
* 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.
*/
public class Solution {
/**
* dfs
* @param root
* @param sum
* @return
*/
public boolean hasPathSum_error(TreeNode root, int sum) {
if(root==null)
return false;
return dfs(root, 0, sum, 0);
}
boolean dfs(TreeNode cur, int sum_cur, int sum, int depth) {
if(cur==null) {
if(sum_cur==sum&&depth>1)
return true;
else
return false;
}
return dfs(cur.left, sum_cur+cur.val, sum, depth+1) || dfs(cur.right, sum_cur+cur.val, sum, depth+1);
}
public boolean hasPathSum(TreeNode root, int sum) {
return dfs(root, sum);
}
/**
* TreeNode val can be negative
* @param c
* @param remain
* @return
*/
boolean dfs(TreeNode c, int remain) {
if(c==null)
return false;
remain -= c.val;
if(remain==0&&c.left==null&&c.right==null)
return true;
return dfs(c.left, remain) || dfs(c.right, remain);
}
}