Leetcode: Path Sum

Path Sum | LeetCode OJ

We need to find whether sum of any path in the tree matches the target. We can use the below algorithm

1. Check if we are at a leaf and target matches the value of the leaf
2. Otherwise recursively check in left subtree for a path with sum equal to target minus the current node value
3. Return true if any of the above checks is true

Remarks:

1. Recursion solutions in trees run for each node hence the time complexity will be O(n)
2. Although we are using constant number of variables i.e. 3, the recursion for each node will make the total space 3*n i.e. O(n)

Extensions:

1. Find sum of all path of a tree
2. Find all path of a tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        c1 = sum == root.val and not root.left and not root.right
        c2 = self.hasPathSum(root.left, sum - root.val)
        c3 = self.hasPathSum(root.right, sum - root.val)
        return c1 or c2 or c3