日野弥生：勉強しよう
LeetCode 112 - 路径总和
发表于2025年02月19日
非递归的方式，可以用BFS,结点出栈时把当前结点的值加到他即将被入栈的左右子节点中。
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
queue = deque()
queue.append(root)
while queue:
curr = queue.popleft()
# 到底了就直接检查是否相等，不等则继续循环
if curr.left is None and curr.right is None:
if curr.val == targetSum:
return True
if curr.left is not None:
curr.left.val += curr.val
queue.append(curr.left)
if curr.right is not None:
curr.right.val += curr.val
queue.append(curr.right)
return False递归的思路则是类似于二叉树深度的计算。
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
if root.left is None and root.right is None:
if root.val == targetSum:
return True
# 如此递归才是精妙
return (self.hasPathSum(root.left, targetSum - root.val) or
self.hasPathSum(root.right, targetSum - root.val))后序遍历思想的递归实现：
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
# 递归遍历左子树和右子树
left_has_path = self.hasPathSum(root.left, targetSum - root.val)
right_has_path = self.hasPathSum(root.right, targetSum - root.val)
# 后序遍历的核心：在访问根节点之前，先访问左右子树
if not root.left and not root.right:
return root.val == targetSum
return left_has_path or right_has_path