题目描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
示例: 给定如下二叉树，以及目标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
解题思路：
这题中明确说明是从根节点到叶子结点的路径，因此递归更简单
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 res = [] def find_route(node, tempSum, tempList): if node is None: return if node.left is None and node.right is None: if tempSum == node.val: tempList.append(node.val) res.append(tempList) else: return find_route(node.left, tempSum - node.val, tempList + [node.val]) find_route(node.right, tempSum - node.val, tempList + [node.val]) find_route(root, sum, []) return True if len(res) > 0 else False n5 = TreeNode(5) n4 = TreeNode(4); n8 = TreeNode(8) n11 = TreeNode(11); n13 = TreeNode(13); n3 = TreeNode(4) n7 = TreeNode(7); n2 = TreeNode(2); n1 = TreeNode(1) n5.left = n4; n5.right = n8 n4.left = n11; n8.left = n13; n8.right = n3 n11.left = n7; n11.right = n2; n3.right = n1 S = Solution() print(S.hasPathSum(n5, 22))