leetcode 112 路径总和

俺的写法是递归找到每一条路径，算出总和添加到一个列表中，在判断存在不存在。

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

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        self.path = []
        self.getSum(root, 0)
        return sum in self.path

    def getSum(self, root, temp):
        if not root.left and not root.right:
            t = root.val + temp
            self.path.append(t)
        if root.left:
            t = root.val + temp
            self.getSum(root.left, t)
        if root.right:
            t = root.val + temp
            self.getSum(root.right, t)
        

看了下比较好的写法，直接用给的和递归减去节点值，判断相等不相等。

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

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root is None:
            return False
        if root.left is None and root.right is None:
            return sum == root.val
        else:
            return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)