iven 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.
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.
Return 0 / 1 ( 0 for false, 1 for true ) for this problem
Method:
DFS
Solution:
Time: O(n) Space: O(1)
/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { * val = x; * left=null; * right=null; * } * } */ public class Solution { public int hasPathSum(TreeNode A, int B) { if (A == null) return 0; if (A.left == null && A.right == null) { return A.val == B ? 1 : 0; } if (A.left == null) { return hasPathSum(A.right, B - A.val); } if (A.right == null) { return hasPathSum(A.left, B - A.val); } int left = hasPathSum(A.left, B - A.val); int right = hasPathSum(A.right, B - A.val); return Math.max(left, right); } }