Given a tree and a sum , return true if there is a path from the root down to a leaf , such that adding up all the values along the path equals the given sum . Strategy : subtract the node value from the sum when recurring down , and check to see if the sum is 0 when you run out of tree . s is the sum
def hasPathSum ( node , s ) : NEW_LINE INDENT if node is None : NEW_LINE INDENT return ( s == 0 ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = 0 NEW_LINE subSum = s - node . data NEW_LINE if ( subSum == 0 and node . left == None and node . right == None ) : NEW_LINE INDENT return True NEW_LINE DEDENT if node . left is not None : NEW_LINE INDENT ans = ans or hasPathSum ( node . left , subSum ) NEW_LINE DEDENT if node . right is not None : NEW_LINE INDENT ans = ans or hasPathSum ( node . right , subSum ) NEW_LINE DEDENT return ans NEW_LINE DEDENT DEDENT