hasPathSum.py

'''
Source : https://leetcode.com/problems/path-sum/
Author : Yuan Wang
Date   : 2018-07-31

/********************************************************************************** 
*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 = 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.
**********************************************************************************/
'''

# Definition for a binary tree node.
# class TreeNode:
#	 def __init__(self, x):
#	 self.val = x
#	 self.left = None
#	 self.right = None


#Time complexity:O(n) Space complexity:O(1)
def hasPathSum(self, root, sum):
	"""
	:type root: TreeNode
	:type sum: int
	:rtype: bool
	"""
	if not root:
		return False
	
	if not root.left and not root.right:
		return sum == root.val
	
	return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)