-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPathSum_112.java
More file actions
117 lines (108 loc) · 3.5 KB
/
Copy pathPathSum_112.java
File metadata and controls
117 lines (108 loc) · 3.5 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package com.leetcode.tree;
import java.util.Stack;
/**
* Created by charles on 4/9/17.
* 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.
*/
public class PathSum_112 {
/**
* Because premise is to find sum from root to leaf
* if (current node is leaf) {
* when root.left == null && root.right == null
* return sum == root.val
* }
* backtrack
* bool sum of left tree || bool of sum of right tree
* where target sum is prev sum - root.val
*/
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
return helper(root, sum);
}
private boolean helper(TreeNode root, int target) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return target == root.val;
}
return helper(root.left, target - root.val) || helper(root.right, target - root.val);
}
/** iteration solution
* use two Stacks, one is to simulate to keep track of tree node
* the other is to record sub sum of each path until leaf */
public boolean hashPathSumII(TreeNode root, int sum) {
if (root == null) {
return false;
}
Stack<TreeNode> path = new Stack<>();
Stack<Integer> sums = new Stack<>();
path.push(root);
sums.push(root.val);
TreeNode node = null;
int sub = 0;
while (!path.isEmpty()) {
node = path.pop();
sub = sums.pop();
// check if node is leaf node in the tree
if (node.left == null && node.right == null) {
// then check current sub sum is target sum
if (sub == sum) {
return true;
}
} else {
if (node.left != null) {
path.push(node.left);
sums.push(node.left.val + sub);
}
if (node.right != null) {
path.push(node.right);
sums.push(node.right.val + sub);
}
}
}
return false;
}
/** better solution, use backtrack thought in stack of value sum */
public boolean hasPathSumIII(TreeNode root, int sum) {
if (root == null) {
return false;
}
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> sums = new Stack<>();
stack.push(root);
sums.push(sum); // push target sum at the beginning
int target = 0;
TreeNode node = null;
while (!stack.isEmpty()) {
target = sums.pop();
node = stack.pop();
// if node is leaf
if (node.left == null && node.right == null && node.val == target) {
return true;
}
/** for this question, sequence of left or right isn't matter */
if (node.right != null) {
stack.push(node.right);
sums.push(target - node.val);
}
if (node.left != null) {
stack.push(node.left);
sums.push(target - node.val);
}
}
return false;
}
}