如何不使用队列实现二叉树的层序插入？

需要构建一棵按层序插入用户输入数据的二叉树，但现有Java教程大多是排序插入的实现。尝试了GFG的层序插入方法，用了Queue但被判0分，现在需要实现无队列的层序插入。

GFG的队列实现方法（结果正确但用了队列） #

输入1 2 3 4 5 6 7，中序遍历输出4 2 5 1 6 3 7，代码如下：

void addData(int data) {
    Node newNode = new Node(data);

    if (root == null) {
        root = newNode;
    } else {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (true) {
            Node node = queue.remove();

            if (node.left != null && node.right != null) {
                queue.add(node.left);
                queue.add(node.right);
            }
            else {
                if (node.left == null) {
                    node.left = newNode;
                    queue.add(node.left);
                } else {
                    node.right = newNode;
                    queue.add(node.right);
                }
                break;
            }
        }
    }
}

现有理解的无队列实现（排序插入，不符合需求） #

输入1 2 3 4 5 6 7，中序遍历输出1 2 3 4 5 6 7，代码如下：

private Node insertNode(Node current, int data) {
    if (current == null) {
        return new Node(data);
    }

    if (data < current.data) {
        current.left = insertNode(current.left, data);
    }
    else if (data > current.data) {
        current.right = insertNode(current.right, data);
    }
    else {
        return current;
    }

    return current;
}

public void addNode(int data) {
    root = insertNode(root, data);
}

我的完整代码（目前用的是排序插入） #

import java.util.Scanner;

public class BinaryTree {
    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
            right = left = null;
        }
    }

    public static class treeBinary {
        Node root;

        treeBinary() {
            root = null;
        }

        private Node insertNode(Node current, int data) {
            if (current == null) {
                return new Node(data);
            }

            if (data < current.data) {
                current.left = insertNode(current.left, data);
            }
            else if (data > current.data) {
                current.right = insertNode(current.right, data);
            }
            else {
                return current;
            }

            return current;
        }

        public void addNode(int data) {
            root = insertNode(root, data);
        }

        public void inorderPrint(Node node) {
            if (node != null) {
                inorderPrint(node.left);
                System.out.print(" " + node.data);
                inorderPrint(node.right);
            }
        }

        void inorderPrint() {
            inorderPrint(root);
        }

        public void preorderPrint(Node node) {
            if (node != null) {
                System.out.print(" " + node.data);
                preorderPrint(node.left);
                preorderPrint(node.right);
            }
        }

        void preorderPrint() {
            preorderPrint(root);
        }

        public void postorderPrint(Node node) {
            if (node != null) {
                postorderPrint(node.left);
                postorderPrint(node.right);
                System.out.print(" " + node.data);
            }
        }

        void postorderPrint() {
            postorderPrint(root);
        }
    }

    public static void main(String[] args) {
        Scanner inputUser = new Scanner(System.in);
        treeBinary userBT = new treeBinary();
        boolean userChoice = false;
        int count = 0;

        mainMenu:
        do {
            System.out.println("\n\n\n1 - Add Data");
            System.out.println("2 - Print (In-Order)");
            System.out.println("3 - Print (Pre-Order");
            System.out.println("4 - Print (Post-Order)");
            System.out.println("5 - Exit");

            System.out.print("Enter your choice: ");
            switch (inputUser.nextInt()) {
                case 1:
                    System.out.print("How many will you input? ");
                    int x = inputUser.nextInt();

                    for (int i = 0; i < x; i++) {
                        System.out.print("Input Data " + (count+1) + ": ");
                        userBT.addNode(inputUser.nextInt());
                        count++;
                    }

                    break;

                case 2:
                    System.out.println("The Tree in In-Order: ");
                    userBT.inorderPrint();

                    break;

                case 3:
                    System.out.println("The Tree in Pre-Order: ");
                    userBT.preorderPrint();

                    break;

                case 4:
                    System.out.println("The Tree in Post-Order: ");
                    userBT.postorderPrint();

                    break;

                case 5:
                    break mainMenu;

                default:
                    System.out.println("Invalid Input!");
            }
        }
        while (!userChoice);
    }
}

无队列的层序插入实现方案 #

层序插入的核心是按层从左到右填充空节点，不用队列的话，可以利用完全二叉树的索引特性（根节点索引为1，左子节点为2*索引，右子节点为2*索引+1）来实现：

步骤1：添加节点计数方法 #

先实现一个计算当前树总节点数的方法，用于确定新节点的插入位置：

private int countNodes(Node node) {
    if (node == null) return 0;
    return 1 + countNodes(node.left) + countNodes(node.right);
}

步骤2：实现递归的层序插入方法 #

通过递归遍历，根据索引找到对应的插入位置：

private Node insertByIndex(Node node, int data, int index, int totalNodes) {
    if (node == null) {
        // 插入前总节点数为totalNodes，新节点的索引是totalNodes+1
        if (index == totalNodes + 1) {
            return new Node(data);
        }
        return null;
    }
    // 先递归查找左子树的插入位置
    Node leftNode = insertByIndex(node.left, data, 2 * index, totalNodes);
    if (leftNode != null) {
        node.left = leftNode;
        return node;
    }
    // 左子树没找到则递归查找右子树
    Node rightNode = insertByIndex(node.right, data, 2 * index + 1, totalNodes);
    if (rightNode != null) {
        node.right = rightNode;
        return node;
    }
    return null;
}

步骤3：修改对外的addNode方法 #

替换原来的排序插入逻辑，调用新的层序插入方法：

public void addNode(int data) {
    int totalNodes = countNodes(root);
    root = insertByIndex(root, data, 1, totalNodes);
}

修改完成后，输入1 2 3 4 5 6 7，中序遍历会输出4 2 5 1 6 3 7，完全符合层序插入的要求，且没有使用队列。

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