[数据结构与算法]leetcode112 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

广度优先

记录从根节点到当前节点的路径和，广度优先保证每个节点只进入一次，防止重复计算。这样我们使用两个队列，分别存储将要遍历的节点，以及根节点到这些节点的路径和即可。
时间复杂度：O(n)，其中 n 是树的节点数
空间复杂度：O（n），其中 n 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def bfs(self, root, target):
        if not root:
            return False
        queue = []
        queue_sum = []
        queue.append(root)
        queue_sum.append(root.val)
        while queue and queue[0]:
            size = len(queue)
            for _ in range(size):
                cur =queue.pop(0)
                cur_sum = queue_sum.pop(0)
                if (not cur.left) and (not cur.right) and (cur_sum == target):
                        return True
                if cur.left:
                    queue.append(cur.left)
                    queue_sum.append(cur_sum + cur.left.val)
                if cur.right:
                    queue.append(cur.right)
                    queue_sum.append(cur_sum + cur.right.val)
        return False
        
        
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        return self.bfs(root, targetSum)
    

递归
对根节点来说，当前节点的值是 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 target - val, 也就是把子节点作为递归函数的根节点，把target-val作为递归函数的目标。边界是，若当前节点就是叶子节点其值为val，是否存在从当前节点的子节点到叶子的路径，满足其路径和为 target - val=0

时间复杂度：O(n)，其中 n 是树的节点数
空间复杂度：O（logn），其中 n 是树的节点数。空间复杂度主要取决递归栈

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if (not root.left) and (not root.right):
            return root.val == targetSum
        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)