112. 路径总和

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

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:

        # 节点为空时，直接返回False
        if not root:
            return False
        
        # 当到达叶子节点时，判断当前节点值与剩下的和是否相等
        if not root.left and not root.right:
            return sum == root.val
        
        # 递归的去判断左子树和右子树，不断缩小问题规模(要查找的值变为sum-root.val)
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)