Easy

给定二叉树和一个目标值，判断该树是否包含一条跟到叶的路径，其和值为给定目标值。

Example:
给定以下二叉树和目标值22,
5
/
4 8
/ /
11 13 4
/ \
7 2 1
返回True, 因为存在根到叶路径 5->4->11->2 的和为22.

我的思路是先求出所有根到叶的和值，然后就能轻易的看出目标值是否被包含。因为有多少个叶子节点就有多少个和值，bottom-top的方法比较合适，复杂度控制在O(N)

# 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: 
            sums = []
        else:
            sums = self.sums_all(root)
        return sum in sums
        
    def sums_all(self, root):
        if not root.left and not root.right: return [root.val]
        elif root.left and not root.right: return [root.val+x for x in self.sums_all(root.left)]
        elif not root.left and root.right: return [root.val+x for x in self.sums_all(root.right)]
        else: return [root.val+x for x in self.sums_all(root.left)] + [root.val+x for x in self.sums_all(root.right)]

参见leetcode上其他coder的思路，发现下面这个解法更加简便直接。虽然是top-bottom的解法，复杂度甚至比上面的方法更简单，最糟糕的情况是O(N)。

    def hasPathSum(self, root, sum):
        if not root: return False
        if not root.left and not root.right and root.val == sum: return True
        sum -= root.val
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)