BFS遍历队列出现null原因与边界处理技巧

本文深入剖析了在LeetCode 116题“填充每个节点的下一个右侧节点指针”的BFS实现中，队列中出现null值的真实原因——并非子节点处理失误，而是根节点为空时直接将null加入初始队列所致；文章强调必须在算法入口处显式判空并快速返回，而非在循环内用临时if(curr == null) break掩盖问题，从而提升代码健壮性、可读性与可维护性，并延伸说明了peek()行为的合理性及完美二叉树下的安全拓展逻辑，揭示了高质量算法实现的核心原则：边界处理要前置、清晰、彻底。

本文解析 LeetCode「填充每个节点的下一个右侧节点指针」题中 BFS 实现里 `curr == null` 的成因：根本原因是输入根节点可能为 `null`（空树），而非子队列误入空值；正确做法是在入口处统一判空，而非在循环内临时拦截。

在实现二叉树层序遍历（BFS）类题目时，一个常见但易被忽视的细节是空树（root == null）的边界处理。以 LeetCode 116 题 Populating Next Right Pointers in Each Node 为例，题目明确说明节点数可以为 0，即输入 root 可能直接为 null。

回顾原始代码：

public Node connect(Node root) {
    Queue<Node> q = new LinkedList<>();
    q.add(root); // ⚠️ 若 root 为 null，此处已将 null 入队

    while(!q.isEmpty()) {
        Queue<Node> childQ = new LinkedList<>();
        while(!q.isEmpty()) {
            Node curr = q.remove();
            if(curr == null) break; // 临时补丁：掩盖了根本问题
            curr.next = q.peek();
            if(curr.left != null) {
                childQ.add(curr.left);
                childQ.add(curr.right);
            }
        }
        q = childQ;
    }
    return root;
}

问题核心在于：q.add(root) 这一行——当 root == null 时，null 被直接加入初始队列。随后进入外层 while 循环，内层 q.remove() 取出该 null，触发 if(curr == null) break 才避免空指针异常。这不是 childQ 引入了 null，而是初始队列从源头就携带了 null。

✅ 正确且专业的处理方式是：在算法逻辑开始前，显式检查并快速返回，保持主循环体的简洁性与健壮性：

public Node connect(Node root) {
    if (root == null) {  // ✅ 标准化边界处理：空树直接返回
        return root;
    }

    Queue<Node> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
        Queue<Node> childQ = new LinkedList<>();
        while (!q.isEmpty()) {
            Node curr = q.remove();
            curr.next = q.peek(); // 此时 curr 必不为 null

            // 只有非空节点才拓展子节点（题目保证完美二叉树，left/right 同存同缺）
            if (curr.left != null) {
                childQ.add(curr.left);
                childQ.add(curr.right);
            }
        }
        q = childQ;
    }
    return root;
}

? 关键注意事项：

• 不要依赖循环内 null 检查来“兜底”，它会掩盖设计缺陷，降低可读性，并可能在后续修改中埋下隐患；
• q.peek() 在 q 非空时返回队首元素，若队列为空则返回 null——这恰好符合题意中“最右节点的 next 应为 null”的要求，无需额外判断；
• 本题为完美二叉树，curr.left != null 即隐含 curr.right != null，故可安全添加两者；若推广到普通二叉树，需分别判空。

总结：BFS 实现中出现 null，首要排查输入参数与初始化逻辑，而非假设中间过程“意外污染”。清晰、前置的边界处理，是高质量算法代码的基石。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《BFS遍历队列出现null原因与边界处理技巧》文章吧，也可关注golang学习网公众号了解相关技术文章。