forked from JojoYang666/Leetcode-1-300
-
Notifications
You must be signed in to change notification settings - Fork 0
/
_112_PathSum.java
68 lines (63 loc) · 2.2 KB
/
_112_PathSum.java
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
package leetcode_1To300;
import java.util.Stack;
/**
* 本代码来自 Cspiration,由 @Cspiration 提供
* 题目来源:http://leetcode.com
* - Cspiration 致力于在 CS 领域内帮助中国人找到工作,让更多海外国人受益
* - 现有课程:Leetcode Java 版本视频讲解(1-900题)(上)(中)(下)三部
* - 算法基础知识(上)(下)两部;题型技巧讲解(上)(下)两部
* - 节省刷题时间,效率提高2-3倍,初学者轻松一天10题,入门者轻松一天20题
* - 讲师:Edward Shi
* - 官方网站:https://cspiration.com
* - 版权所有,转发请注明出处
*/
public class _112_PathSum {
/**
* 112. Path Sum
* 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.
time : O(n);
space : O(n);
* @param root
* @param sum
* @return
*/
public static boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null) {
return sum == root.val;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
public static boolean hasPathSum2(TreeNode root, int sum) {
if (root == null) return false;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
if (cur.left == null && cur.right == null) {
if (cur.val == sum) {
return true;
}
}
if (cur.right != null) {
stack.push(cur.right);
cur.right.val += cur.val;
}
if (cur.left != null) {
stack.push(cur.left);
cur.left.val += cur.val;
}
}
return false;
}
}