"""
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
示例 3：

输入：root = [1,2], targetSum = 0
输出：false
"""
class Solution(object):
    def hasPathSum(self, root, targetSum):
        if not root: return False
        def path(root1, target):
            if not root1: return False
            target -= root1.val
            if not root1.left and not root1.right:
                if not target:
                    return True
                else:
                    return False
            return path(root1.left, target) or path(root1.right, target)
        return path(root, targetSum)

class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    res = Solution().hasPathSum(root, 4)
    print(res)