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 path5->4->11->2which sum is 22.

Analysis:

Recursive approach, see code. Be aware that, in this type of recursion, no need to change curSum at the end of recursion, since this is pass by value(primitive), changes on curSum in one recursion does not reflect on other recursion. If this is a list instead of primitive, then we need to delete/pop/poll from it to make sure the changes on list does not affect other recursion.

Complexity:

Time: O(N)

Space: O(logn)

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null)
        {
            return false;
        }
        return traverse(root, sum, 0);
    }

    private boolean traverse(TreeNode root, int sum, int curSum)
    {
        if(root == null)
        {
            return false;
        }
        if(root.left == null && root.right == null && curSum + root.val == sum)
        {
            return true;
        }

        return traverse(root.left, sum, curSum+root.val) || traverse(root.right, sum, curSum + root.val);
    }
}