二叉搜索树按深度显示节点异常，欲基于2^depth逻辑实现求解

插入OPTIMAL后的二叉搜索树为完全二叉树结构：根节点O，左子节点P、右子节点I；P的左子节点T、右子节点M；I的左子节点A、右子节点L，各层节点数严格符合2^depth。

以下是按层遍历输出节点字符的代码：

void wordsAtDepth() {
        int depth = 0;
        int numOfNodes;
        Queue queue = new Queue(32); // 创建队列
        queue.insert(root); // 根节点入队

        // 队列非空则继续循环
        while (!queue.isEmpty()) {
            // 当前层的节点数按2^depth计算
            numOfNodes = (int) Math.pow(2, depth);
            // 遍历当前层所有节点
            for (int i = 0; i < numOfNodes; i++) {
                // 取出队首节点
                Node Current = queue.remove();
                // 节点非空则输出，并将左右子节点入队
                if(Current != null){
                    System.out.print(Current.cData);
                    queue.insert(Current.leftChild);
                    queue.insert(Current.rightChild);
                }
            }
            // 换行分隔不同层
            System.out.println(" ");
            depth++;
        }
    }

节点存储字符值，输入OPTIMAL时输出正常，但输入HAPPY、SUPERMAN等单词时输出异常，例如SUPERMAN的输出为：S PU ER AMN SPUERAMNPUERAMN ERAMNAMNNEMNNAMNN AMNNNNAMNNNNNNNN NNNNNNNN。

目前将numOfNodes = (int) Math.pow(2, depth);替换为numOfNodes = queue.length();可正常工作，但希望保留2^depth的实现逻辑（理论上二叉树某深度的节点数为2^depth），需解决输出异常问题。

核心问题：只有完全二叉树的每一层节点数才严格等于2^depth，插入HAPPY、SUPERMAN后的二叉搜索树不是完全二叉树，存在大量空节点，但原代码遇到空节点时，没有向队列中插入对应的空左/右子节点，导致队列实际节点数与2^depth不匹配；同时当队列已空时，depth仍在递增，for循环会继续执行，从空队列取节点会导致重复输出或逻辑混乱。

修复步骤：

1. 遇到空节点时，也向队列插入两个null，保证每一层的节点数始终是2^depth，维持层级结构的完整性。
2. 每一层处理完后，检查队列中是否全为null，如果是则终止循环，避免后续无效的空行和循环。

修复后的代码：

void wordsAtDepth() {
    int depth = 0;
    int numOfNodes;
    Queue queue = new Queue(32);
    queue.insert(root);

    while (!queue.isEmpty()) {
        numOfNodes = (int) Math.pow(2, depth);
        boolean allNull = true; // 标记当前层处理后队列是否全为null
        for (int i = 0; i < numOfNodes; i++) {
            Node Current = queue.remove();
            if (Current != null) {
                System.out.print(Current.cData);
                queue.insert(Current.leftChild);
                queue.insert(Current.rightChild);
                // 只要有一个非空子节点，后续队列就不全是null
                if (Current.leftChild != null || Current.rightChild != null) {
                    allNull = false;
                }
            } else {
                // 空节点也要插入两个null，维持层级节点数
                queue.insert(null);
                queue.insert(null);
            }
        }
        System.out.println(" ");
        depth++;
        // 如果队列全是null，终止循环，避免无限处理空层
        if (allNull) {
            break;
        }
    }
}

说明：

• 插入空节点的操作保证了每一层的节点数严格符合2^depth，和理论逻辑匹配。
• allNull标记避免了后续对全空层的无效处理，防止输出大量空行或重复内容。

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