Root to leaf path sum equal to a given number | A binary tree node ; 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 ; Constructed binary tree is 10 / \ 8 2 / \ / 3 5 2
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT 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 s = 21 NEW_LINE root = Node ( 10 ) NEW_LINE root . left = Node ( 8 ) NEW_LINE root . right = Node ( 2 ) NEW_LINE root . left . right = Node ( 5 ) NEW_LINE root . left . left = Node ( 3 ) NEW_LINE root . right . left = Node ( 2 ) NEW_LINE if hasPathSum ( root , s ) : NEW_LINE INDENT print " There ▁ is ▁ a ▁ root - to - leaf ▁ path ▁ with ▁ sum ▁ % d " % ( s ) NEW_LINE DEDENT else : NEW_LINE INDENT print " There ▁ is ▁ no ▁ root - to - leaf ▁ path ▁ with ▁ sum ▁ % d " % ( s ) NEW_LINE DEDENT