力扣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); } }

算法流程

检查当前节点是否为空，空节点返回false
如果是叶子节点（左右子节点都为空），判断targetSum == root.val
如果不是叶子节点，递归检查左右子树，更新targetSum = targetSum - root.val
左右子树任意一条路径满足条件即返回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; } }

算法流程

初始化两个队列，分别存储节点和对应的路径和
将根节点和其值加入队列
循环处理队列中的元素：
- 取出节点和对应的路径和
- 如果是叶子节点，检查路径和是否等于目标值
- 如果不是叶子节点，将子节点及新的路径和加入队列
遍历完所有节点后未找到返回false

复杂度分析

时间复杂度：O(N)，每个节点访问一次
空间复杂度：O(N)，队列最多存储所有节点

两种解法的对比

特性	递归DFS	迭代BFS
实现方式	递归调用	队列迭代
遍历顺序	深度优先	广度优先
空间复杂度	O(H)，H为树高度	O(N)，最坏情况
代码简洁性	简洁优雅	相对复杂
栈溢出风险	树很深时可能溢出	无递归栈溢出风险
适用场景	树较平衡时	树很宽或需要避免递归时

关键点总结

1. 叶子节点的判断

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

2. 路径和的计算

DFS：通过递归参数传递更新后的目标值（targetSum - node.val）
BFS：通过第二个队列存储从根节点到当前节点的累计和

3. 边界条件处理

空树（root == null）直接返回false
单节点树需要作为叶子节点处理

常见错误

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

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

未正确处理空节点：对空节点进行.val操作会导致空指针异常
未更新目标值：在递归或迭代时忘记减去当前节点的值

扩展思考

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

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

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; }