开发|leetcode112 路径总和数据结构|算法

【开发|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 Falsedef 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)