Leetcode 112. 路径总和

**LeetCode112. 路径总和**

### 题目描述给定一个二叉树的根节点 `root` 和一个整数 `sum`,判断是否存在从根节点到叶节点的路径，且路径上的每个节点值之和等于 `sum`。

### 示例示例1:

输入: root = [5,4,8,11,null,13,4,7,2], sum =22输出: true解释: 从根到叶的路径为 `[5,4,11,2]`,和为 `22`。

示例2:

输入: root = [1,2,3], sum =100输出: false解释: 没有从根到叶的路径和为100。

### 解决方案#### 方法一：递归法我们可以使用递归来解决这个问题。每次递归时，我们都会检查当前节点是否等于 `sum`，如果是，则返回 `True`。否则，我们会继续递归到左子树和右子树。

# Definition for a binary tree node.
class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef hasPathSum(root: TreeNode, sum: int) -> bool:
 # Base case: 如果根节点为空，则返回 False。
 if not root:
 return False # 如果当前节点值等于和，则返回 True。
 if root.val == sum and (not root.left and not root.right):
 return True # 递归到左子树和右子树，检查是否有路径和为 sum 的叶节点。
 return hasPathSum(root.left, sum - root.val) or hasPathSum(root.right, sum - root.val)

#### 方法二：迭代法我们可以使用队列来实现迭代法。每次迭代时，我们都会检查当前节点是否等于 `sum`，如果是，则返回 `True`。否则，我们会继续迭代到左子树和右子树。

from collections import dequedef hasPathSum(root: TreeNode, sum: int) -> bool:
 # Base case: 如果根节点为空，则返回 False。
 if not root:
 return False queue = deque([(root, root.val)])
 while queue:
 node, total = queue.popleft()
 # 如果当前节点值等于和，并且没有子树，则返回 True。
 if node.left is None and node.right is None and total == sum:
 return True # 添加左子树和右子树到队列中。
 if node.left:
 queue.append((node.left, total + node.left.val))
 if node.right:
 queue.append((node.right, total + node.right.val))
 # 如果没有找到路径，则返回 False。
 return False

###代码注释* `hasPathSum` 函数接受一个二叉树的根节点 `root` 和一个整数 `sum` 作为输入。
* 基于情况，函数会递归或迭代地检查当前节点是否等于 `sum`，并且没有子树。
* 如果找到路径，则返回 `True`；否则，返回 `False`。

### 总结本文介绍了 LeetCode112. 路径总和 的解决方案。我们使用递归法和迭代法来实现该函数。每种方法都有其优缺点，选择哪种方法取决于具体的场景和需求。