Path Sum

Problem: Path Sum

We can use a stack to implement depth-first search and we can use tuples to store sum value and tree nodes in the stack at the same time.

Code in Python:

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root: return False
        stack = [(root, 0)]
        while stack:
            cur = stack.pop()
            if not cur[0].left and not cur[0].right:
                if cur[1] + cur[0].val == sum:
                    return True
                continue
            if cur[0].right:
                stack.append((cur[0].right, cur[1]+cur[0].val))
            if cur[0].left:
                stack.append((cur[0].left, cur[1]+cur[0].val))
        return False