Question
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.
Stats
| Frequency | 3 |
| Difficulty | 1 |
| Adjusted Difficulty | 1 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This question can be solved with either DFS or BFS.
Solution
My code is DFS recursion.
I found another BFS non-recursive solution here, but I did not post this code, because this question is too simple.
One more thing, the last line of code has a || operation. Isn’t it duplicate execution? I mean if answer is found in root.left, no need to check root.right.
Actually it’s not duplication. The official doc explains it:
The && and || operators perform Conditional-AND and Conditional-OR operations on two boolean expressions. These operators exhibit “short-circuiting” behavior, which means that the second operand is evaluated only if needed.
Code
public 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);
}