力扣112. 路径总和：递归DFS vs 迭代BFS

题目描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

示例：

给定如下二叉树，以及目标和 sum = 22 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 返回 true，因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

解法一：递归DFS（深度优先搜索）

核心思想

采用深度优先搜索策略，从根节点开始递归遍历每条路径。每次递归时，用目标和减去当前节点的值，当到达叶子节点时判断剩余值是否等于叶子节点的值。

代码实现

class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { // 空节点直接返回false if (root == null) { return false; } // 如果是叶子节点，判断当前值是否等于剩余的targetSum if (root.left == null && root.right == null) { return targetSum == root.val; } // 递归检查左右子树 return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); } }

算法流程

1. 检查当前节点是否为空，空节点返回false

2. 如果是叶子节点（左右子节点都为空），判断targetSum == root.val

3. 如果不是叶子节点，递归检查左右子树，更新targetSum = targetSum - root.val

4. 左右子树任意一条路径满足条件即返回true

复杂度分析

• 时间复杂度：O(N)，每个节点访问一次

• 空间复杂度：O(H)，递归栈的深度为树的高度H，最坏情况O(N)

解法二：迭代BFS（广度优先搜索）

核心思想

使用队列进行广度优先遍历，同时维护从根节点到当前节点的路径和。通过两个队列（一个存储节点，一个存储路径和）实现同步遍历。

代码实现

class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; Queue<TreeNode> nodeQueue = new LinkedList<>(); Queue<Integer> valueQueue = new LinkedList<>(); nodeQueue.offer(root); valueQueue.offer(root.val); while (!nodeQueue.isEmpty()) { TreeNode currentNode = nodeQueue.poll(); int currentSum = valueQueue.poll(); // 如果是叶子节点，检查路径和 if (currentNode.left == null && currentNode.right == null) { if (currentSum == sum) return true; continue; } // 将子节点和新的路径和加入队列 if (currentNode.left != null) { nodeQueue.offer(currentNode.left); valueQueue.offer(currentSum + currentNode.left.val); } if (currentNode.right != null) { nodeQueue.offer(currentNode.right); valueQueue.offer(currentSum + currentNode.right.val); } } return false; } }

算法流程

1. 初始化两个队列，分别存储节点和对应的路径和

2. 将根节点和其值加入队列

3. 循环处理队列中的元素：

   • 取出节点和对应的路径和

   • 如果是叶子节点，检查路径和是否等于目标值

   • 如果不是叶子节点，将子节点及新的路径和加入队列

4. 遍历完所有节点后未找到返回false

复杂度分析

• 时间复杂度：O(N)，每个节点访问一次

• 空间复杂度：O(N)，队列最多存储所有节点

两种解法的对比

关键点总结

1. 叶子节点的判断

两种解法都必须正确处理叶子节点的判断：只有当节点的左右子节点都为空时，才是叶子节点。

2. 路径和的计算

• DFS：通过递归参数传递更新后的目标值（targetSum - node.val）

• BFS：通过第二个队列存储从根节点到当前节点的累计和

3. 边界条件处理

• 空树（root == null）直接返回false

• 单节点树需要作为叶子节点处理

常见错误

1. 忽略叶子节点判断：将中间节点的路径和误判为满足条件

   // 错误示例 if (targetSum == 0) return true; // 可能在中途节点就满足了

2. 未正确处理空节点：对空节点进行.val操作会导致空指针异常

3. 未更新目标值：在递归或迭代时忘记减去当前节点的值

扩展思考

如何返回所有满足条件的路径？

如果需要返回所有路径而不仅仅是判断是否存在，可以使用回溯法：

public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); dfs(root, targetSum, path, result); return result; }

如何统计路径数量？

如果只需要统计路径数量而不需要具体路径，可以简化递归逻辑。

结语

路径总和问题是一个经典的二叉树遍历问题，它很好地展示了DFS和BFS在树结构中的应用。理解并掌握这两种解法有助于解决更复杂的树形路径问题，如：

• LeetCode 113. 路径总和 II（返回所有路径）

• LeetCode 437. 路径总和 III（统计路径数量）

• LeetCode 129. 求根节点到叶节点数字之和

掌握递归思维和迭代思维在算法解题中同等重要，根据具体问题选择合适的方法往往能事半功倍。