03_路径总和

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


# 32ms
class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        解题思路：肯定要找到所有的 根--->叶子节点的路径
        list 为根到每个叶子节点的和
        """
        if not root:
            return False

        # list1 = []
        list2 = []
        def helper(node, cur):
            # list1.append(cur)
            if not node:
                return
            if not node.left and not node.right:
                list2.append(cur)
            if node.left:
                helper(node.left, node.left.val+cur)
            if node.right:
                helper(node.right, node.right.val + cur)
        helper(root, root.val)
        return sum in list2


# leetcode 最优解 这个有点意思 他用的是减法 我用的是加法 not and not是结束条件 和我的一样
class Solution2(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        sum -= root.val
        if not root.right and not root.left:
            return sum == 0
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)


a = TreeNode(5)
b = TreeNode(4)
c = TreeNode(8)
d = TreeNode(11)
e = TreeNode(13)
f = TreeNode(4)
g = TreeNode(7)
h = TreeNode(2)
i = TreeNode(1)
a.left, a.right = b, c
b.left = d
c.left, c.right = e, f
d.left, d.right = g, h
f.right = i

s = Solution()
sum = 10
print(s.hasPathSum(a, sum))