Path Sum Link
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 = 23,
6
/ \
4 7
/ / \
3 5 8
/ \ / \
2 10 2 9
return true, as there exist a root-to-leaf path 6->7->8->2 which sum is 23.
Solution:
Since traversing through each and every node is must, we can apply our solution with recursion here. We will recursively go to every node untill the node is leaf that is untill we reach at the bottom and check our required solution. The sum, at every step, will decrease with the current node.
Implementation:
Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
sum -= root.val;
if ((root.left == null) && (root.right == null))
return (sum == 0);
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}
Complexity Analysis:
- Time Complexity: O(n).
- Space Complexity: O(n), for the worst case and O(n), for the best possible case.
