友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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.
Note: A leaf is a node with no children.
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.
解题分析
减去当前节点值的只，然后递归调用，到叶子节点和目标值相等即可。
注意把代码写简化点！
这道题和 129. Sum Root to Leaf Numbers 类似。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Path Sum.
* Memory Usage: 39.1 MB, less than 5.88% of Java online submissions for Path Sum.
*/
public boolean hasPathSum(TreeNode root, int sum) {
if (Objects.isNull(root)) {
return false;
}
sum -= root.val;
if ( Objects.isNull(root.left) && Objects.isNull(root.right)) {
return sum == 0;
}
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
1
2
3
4
5
6
7
8
9
10
public boolean hasPathSum(TreeNode root, int sum) {
if (Objects.isNull(root)) {
return false;
}
if (root.val == sum && root.left == null && root.right == null) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
很简单的一道题。本来是想找另外一道题（见 思考题），结果找到了这道题。
也可以利用回溯来解答。如图：
