Python, preorder traversal


  • 0
    P

    The idea is to do preorder traversal and maintain the sum value from root to current node, if at any time the sum is zero and the current node is a leaf node, we have found a path where the node values sum to given sum.

    class Solution(object):
    
        __slots__ = 'res'
        
        def __init__(self):
            self.res = False
            
        def hasPathSum(self, r, s):
            """
            :type root: TreeNode
            :type sum: int
            :rtype: bool
            """
            def preOrder(root, sum):
                if root:
                    root.val = sum-root.val
                    sum = root.val
                    # print(root.val, sum)
                    if sum == 0 and root.left is None and root.right is None:
                        # print('FOUND PATH WITH SUM:', s)
                        self.res = True
                    preOrder(root.left, sum)
                    preOrder(root.right, sum)
            preOrder(r, s)
            return self.res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.