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

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

题目描述

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

解题思路

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

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

public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 如果根节点为空，直接返回false
        if (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);
            }
        }

        // 遍历完所有节点仍未找到符合条件的路径，返回false
        return 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

 总结

这种使用双队列的BFS解法具有以下优点：
1.通过两个队列分别维护节点和路径和，逻辑清晰易懂
2. 与传统的树的层序遍历方式一致，便于理解和记忆
3. 可以轻松扩展为求解所有路径或路径详情等变种问题

需要注意的关键点是在判断满足条件时，必须同时满足：
1. 当前节点的路径和等于目标值
2. 当前节点为叶子节点（没有左右子节点）

这种解法是解决路径总和问题的经典方法之一，值得熟练掌握。