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)
