本文共 1633 字，大约阅读时间需要 5 分钟。

为了解决问题，我们可以采用广度优先搜索（BFS）的方法来判断是否存在一条从根节点到叶子节点的路径，使得路径上的节点值之和等于目标和targetSum。

解题思路

我们使用两个队列来实现BFS：一个队列存储需要遍历的节点，另一个队列存储到达这些节点时的路径和。这样可以确保每个节点只被处理一次，避免重复计算。

具体步骤如下：

这种方法的时间复杂度为O(n)，其中n是二叉树的节点数。每个节点只会被访问一次。

代码实现

import java.util.*;
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Queue
   
     queue = new LinkedList<>();
        Queue
    
      pathSum = new LinkedList<>();
        queue.offer(root);
        pathSum.offer(root.val);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            int temp = pathSum.poll();
            if (temp > targetSum) {
                continue;
            }
            if (current.left == null && current.right == null) {
                if (temp == targetSum) {
                    return true;
                }
                continue;
            }
            if (current.left != null) {
                queue.offer(current.left);
                pathSum.offer(temp + current.left.val);
            }
            if (current.right != null) {
                queue.offer(current.right);
                pathSum.offer(temp + current.right.val);
            }
        }
        return false;
    }
}
    
   

代码解释

这种方法确保了每个节点只被处理一次，并且在路径和超过目标和时提前终止，提高了算法的效率。