二叉树中和为某一值的路径(一)

描述 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为n

数据范围： 1.树上的节点数满足 0≤n≤10000 2.每 个节点的值都满足 0∣val∣≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n) 进阶：空间复杂度 O(树的高度)，时间复杂度 O(n)

思路：我感觉二叉树的题基本上都是递归，然后都特别简单。当然还可以遍历，深度优先或广度优先，这道题明显是深度优先，大学有学过，现在基本忘记了，而且遍历写起来比递归麻烦得多。

递归的话很简单，相当于sum减去当前root.val根节点的值，然后计算左右子树是否有路径和为sum-root.val，即左右的sum = sum - root.val，当sum为0，且root为根节点（即root的左右节点都为空的时候）的时候，返回True，否则返回False

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return bool布尔型
#
class Solution:
    def hasPathSum(self , root: TreeNode, sum: int) -> bool:
        # write code here
        if root == None:
            return False
        sum -= root.val
        if (sum == 0) & (root.left == None) & (root.right == None):
            return True
        else:
            return self.hasPathSum(root.left,sum) | self.hasPathSum(root.right,sum)