二叉搜索树（BST）层序遍历问题：链表队列无法正常工作

嘿，从你描述的问题和代码片段来看，自定义链表队列在BST广度遍历中offer失败，大概率是在队列实现或者TreeNode结构上踩了坑，我给你梳理几个最常见的排查方向：

1. 先检查你的MyLinkedQueue实现是否有bug #

自定义队列最容易出错的就是入队逻辑，一定要盯紧这几点：

• 队尾指针的更新：如果是单链表实现的队列，入队时必须把新节点挂到队尾节点的next上，然后把队尾指针移到新节点；如果是空队列（队尾为null），要同时把队头和队尾都指向第一个入队的节点，不然后续操作全乱。
• null节点的处理：offer方法里要不要允许入队null？如果你的BST节点不会是null，那最好在offer里加个判断，避免空指针异常。
• size计数是否正确：isEmpty方法如果是靠size判断的，那每次offer/poll都要记得更新size，不然isEmpty会返回错误结果，导致遍历循环根本跑不起来。

给你贴个靠谱的TreeNode队列实现示例，你可以对照着看：

public class MyLinkedQueue<E> {
    private TreeNode<E> front; // 队头
    private TreeNode<E> rear;  // 队尾
    private int size;

    public boolean offer(TreeNode<E> node) {
        if (node == null) {
            return false; // 拒绝null节点入队
        }
        if (isEmpty()) {
            // 空队列入队第一个元素，队头队尾都指向它
            front = node;
            rear = node;
        } else {
            // 非空队列，挂到队尾next，更新队尾
            rear.next = node;
            rear = node;
        }
        size++;
        return true;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    // 别忘了实现poll方法，不然遍历的时候拿不出节点
    public TreeNode<E> poll() {
        if (isEmpty()) {
            return null;
        }
        TreeNode<E> temp = front;
        front = front.next;
        // 如果队列为空了，队尾也要置null
        if (front == null) {
            rear = null;
        }
        size--;
        return temp;
    }
}

2. 确认TreeNode的结构没搞混 #

你说要保留TreeNode的左右指针，那绝对不能用left/right来做队列的链表指针！很多人会犯这个错：

错误操作：用TreeNode的left或right属性来串联队列节点，这会直接覆盖原来的子节点引用，不仅队列用不了，BST的结构也毁了。

正确的做法是，在你的TreeNode类里，除了left、right、data这几个BST需要的属性，额外加一个TreeNode<E> next属性，专门用来做队列的链表串联。比如：

public class TreeNode<E> {
    E data;
    TreeNode<E> left;
    TreeNode<E> right;
    TreeNode<E> next; // 专门给队列用的指针，不影响BST结构

    public TreeNode(E data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.next = null;
    }
}

3. 检查广度遍历的逻辑细节 #

你的traversalBreadth方法开头没问题，但要注意这几点：

• 初始化队列后，第一个节点入队后，一定要确认队列的isEmpty()返回false，不然循环直接跳过。
• 处理节点时，左/右子节点入队前要先判断是否为null，避免入队null节点（如果你的offer拒绝null的话）。
• 可以在offer方法里加个打印日志，或者debug时看每次offer后的size和队尾节点，确认是不是真的入队成功了。

4. 测试边界情况 #

先拿简单的BST测试：

• 只有根节点的BST，入队是否成功？
• 只有左子树或只有右子树的BST，子节点入队是否成功？
• 有没有可能isEmpty方法写反了？比如把return size == 0写成return size != 0，导致循环根本不执行。

如果这些都排查完还是找不到问题，把你的完整MyLinkedQueue和TreeNode代码贴出来，我帮你精准定位！

内容的提问来源于stack exchange，提问作者Brian B