Leetcode 112: 路径总和

Leetcode 112: 路径总和

问题描述：
给定一个二叉树的根节点 root 和一个目标和 targetSum，判断是否存在从根节点到叶子节点的路径，使路径上所有节点的值相加等于目标和 targetSum。

---

适合面试的解法：递归

解法特点：

• 递归是解决路径和问题的最优实现方式，利用二叉树的递归性质逐步处理每条可能的路径。
• 对每个节点，递归减去当前节点的值，直到叶子节点时检查剩余的 targetSum 是否为零。
• 时间复杂度 (O(n))，空间复杂度 (O(h))（(h) 为树的高度，递归栈的深度），非常适合面试场景。

---

解法思路

核心步骤：

1. 递归分治：

   • 当前节点的路径总和，由其左子树和右子树是否有满足条件的路径决定。
   • 每次递归将 targetSum 减去当前节点的值，抵达叶子时检查剩余的和。

2. 判断叶子节点：

   • 如果当前节点是叶子节点（无左子节点也无右子节点），同时路径总和符合 targetSum，返回 true。

3. 递归终止条件：

   • 如果当前节点为 null，返回 false。
   • 叶子节点时检查 targetSum 是否与节点值相等。

4. 最终逻辑：

   • 对每个节点，递归判断它的左子树和右子树是否满足条件。

---

代码模板：递归法

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {// Step 1: 如果节点为空，返回 falseif (root == null) {return false;}// Step 2: 如果节点是叶子节点，检查是否路径总和满足条件if (root.left == null && root.right == null) {return root.val == targetSum;}// Step 3: 减去当前节点值，从左右子树递归查找路径和int remainingSum = targetSum - root.val;return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum);}
}

---

代码详细注释

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {// Step 1: 递归终止条件// 如果当前节点为 null，没有路径可以满足条件，返回 falseif (root == null) {return false;}// Step 2: 检查叶子节点// 如果当前节点是叶子节点（无左右子节点），检查路径总和是否满足 targetSumif (root.left == null && root.right == null) {return root.val == targetSum; // 如果满足条件，返回 true}// Step 3: 递归处理子树// 更新剩余的路径总和，递归查找左右子树int remainingSum = targetSum - root.val;boolean leftResult = hasPathSum(root.left, remainingSum); // 检查左子树路径总和boolean rightResult = hasPathSum(root.right, remainingSum); // 检查右子树路径总和// Step 4: 返回结果// 如果任意一个子树满足路径总和条件，返回 truereturn leftResult || rightResult;}
}

---

复杂度分析

时间复杂度：

• 每个节点最多被访问一次，时间复杂度为 (O(n))，其中 (n) 是树的节点总数。

空间复杂度：

• 递归栈的深度与树的高度相关：
  • 平衡二叉树的高度为 (O(\log n))，空间复杂度为 (O(\log n))。
  • 完全不平衡二叉树（链表状）的高度为 (O(n))，空间复杂度为 (O(n))。

---

测试用例

示例 1：

输入：

root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

输出：

true

解释：
从根节点到叶子节点的一条路径 5 → 4 → 11 → 2 的总和等于 22。

---

示例 2：

输入：

root = [1,2,3], targetSum = 5

输出：

false

解释：
树中任意路径的总和都不等于 5。

---

示例 3：

输入：

root = [], targetSum = 0

输出：

false

---

如何快速 AC（面试技巧）

1. 树的递归分治思想：

• 每个节点的路径和问题可以归结为子树的路径和问题，递归很自然地处理二叉树。

2. 判断叶子节点的条件：

• 特别强调叶子节点的判断逻辑：必须满足“无左右子节点”且“路径和符合目标 sum”。

3. 时间复杂度分析：

• (O(n))：每节点访问一次，这是二叉树递归常见的复杂度。
• 空间复杂度根据树的高度合理优化。

4. 全局逻辑清晰表达：

• 用递归逻辑分解问题，每一层会贡献新的 targetSum（剩余路径和）。

---

其他解法

方法 2：迭代法（使用栈）

思路：

• 使用栈实现递归的效果，根据路径累加值判断是否符合 targetSum。

代码模板：

import java.util.*;class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) return false; // 如果树为空，直接返回 false// 初始化栈，用于模拟递归逻辑Stack<TreeNode> nodeStack = new Stack<>();Stack<Integer> sumStack = new Stack<>();nodeStack.push(root);sumStack.push(targetSum);// 遍历节点while (!nodeStack.isEmpty()) {TreeNode currentNode = nodeStack.pop();int currentSum = sumStack.pop() - currentNode.val;// 如果是叶子节点，检查路径是否满足条件if (currentNode.left == null && currentNode.right == null && currentSum == 0) {return true;}// 将左右子节点入栈（更新路径和）if (currentNode.right != null) {nodeStack.push(currentNode.right);sumStack.push(currentSum);}if (currentNode.left != null) {nodeStack.push(currentNode.left);sumStack.push(currentSum);}}return false;}
}

---

对比递归与迭代

解法	时间复杂度	空间复杂度	适用场景
递归法	(O(n))	(O(h))	简单树结构，逻辑直观
迭代法	(O(n))	(O(h))（栈存储）	深度较大的树，避免递归栈溢出

---

推荐解法：递归法

适合面试场景：

• 递归法易于实现，逻辑直观，时间复杂度和空间复杂度表现良好。

---

总结：如何快速 AC？

1. 使用递归实现，树的递归逻辑清晰。
2. 判断叶子节点时，特别强调路径和条件。
3. 时间复杂度和空间复杂度分析简洁明了，边界处理完整。

通过递归方法，你可以快速实现并解决问题，同时展示对二叉树递归的掌握，非常适合面试场景！