当前位置：首页 > java >正文

LeetCode 112. 路径总和解题思路详解（BFS算法深入理解）

java 2025/8/11 18:38:23

在刷LeetCode时，遇到了第112题"路径总和"(Path Sum)这道经典的二叉树题目。本文将详细解析使用广度优先搜索(BFS)解决该问题的思路和实现。

题目描述

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

解题思路

本解法采用广度优先搜索(BFS)的方式，通过两个队列分别维护节点和到达该节点的路径和：

1. 使用一个队列存储待访问的节点
2. 使用另一个队列存储从根节点到当前节点的路径和
3. 同时遍历两个队列，检查当前节点是否为叶子节点且路径和等于目标值

public class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {// 如果根节点为空，直接返回falseif (root == null) {return false;}// 使用两个队列分别存储节点和到该节点的路径和Queue<TreeNode> nodeQueue = new LinkedList<>();Queue<Integer> sumQueue = new LinkedList<>();// 将起始节点和初始路径和放入队列nodeQueue.offer(root);sumQueue.offer(root.val);// 开始BFS遍历while (!nodeQueue.isEmpty()) {// 同时取出节点和对应的路径和TreeNode node_temp = nodeQueue.poll();Integer val_temp = sumQueue.poll();// 判断是否为叶子节点且路径和等于目标值if (val_temp != null && val_temp == targetSum && node_temp.left == null && node_temp.right == null) {return true;}// 处理左子节点TreeNode node_Left = node_temp.left;if (node_Left != null) {nodeQueue.offer(node_Left);sumQueue.offer(node_Left.val + val_temp);}// 处理右子节点TreeNode node_Right = node_temp.right;if (node_Right != null) {nodeQueue.offer(node_Right);sumQueue.offer(node_Right.val + val_temp);}}// 遍历完所有节点仍未找到符合条件的路径，返回falsereturn false;}
}

算法分析

时间复杂度
O(N)：其中N是二叉树的节点数。在最坏情况下，我们需要访问二叉树的所有节点。

空间复杂度
O(N)：主要由两个队列的空间开销决定。在最坏情况下，队列中会存储接近N个节点的信息。

算法执行流程示例

假设我们有如下二叉树，目标和为22：

执行过程如下：
1. 初始状态：nodeQueue=[5], sumQueue=[5]
2. 第一次循环：取出5和5，5不是叶子节点，将子节点加入队列
  nodeQueue=[4, 8], sumQueue=[9, 13]
3. 第二次循环：取出4和9，4不是叶子节点，将子节点加入队列
  nodeQueue=[8, 11], sumQueue=[13, 20]
4. 第三次循环：取出8和13，8不是叶子节点，将子节点加入队列
  nodeQueue=[11, 13, 4], sumQueue=[20, 26, 17]
5. 第四次循环：取出11和20，11不是叶子节点，将子节点加入队列
  nodeQueue=[13, 4, 7, 2], sumQueue=[26, 17, 27, 22]
6. 第五次循环：取出13和26，13是叶子节点但和不等于22
7. 第六次循环：取出4和17，4是叶子节点但和不等于22
8. 第七次循环：取出7和27，7是叶子节点但和不等于22
9. 第八次循环：取出2和22，2是叶子节点且和等于22，返回true