如何实现普通二叉树的递归插入函数（非BST）

需求说明：

• 实现**普通二叉树（非二叉搜索树BST）**的递归插入函数
• 插入时需保持树的平衡，严格遵循层序从左到右的顺序填充子节点
• 不关心节点值的大小顺序或重复情况
• 禁止使用队列等辅助数据结构，仅通过递归实现

当前实现代码 #

插入函数 #

TreeNode insert(int data, TreeNode root, boolean isLeft){
    if(root == null){
        root = new TreeNode(data);
    }
    else if(root.left == null){
        root.left = new TreeNode(data);
    }
    else if(root.right == null){
        root.right = new TreeNode(data);
    }
    else{
        if(isLeft){
            insert(data, root.right, false);
        }
        else{
            insert(data, root.left, true);
        }
    }
    return root;
}

初始化代码 #

public static void main(String[] args){
    TreeNode root = new TreeNode(1);
    boolean isLeft = false;
    for(int i = 2; i < 11; i++){
        isLeft = !isLeft;
       root = root.insert(i, root, isLeft);
    }
}

问题现状 #

当前代码生成的树结构未达到预期的层序从左到右插入的平衡效果：

实际生成结构 #

│       ┌── 7
│   ┌── 3
│   │   └── 5
│   │       └── 9
└── 1
    │       ┌── 10
    │   ┌── 6
    │   │   └── 8
    └── 2
        └── 4

理想目标结构 #

│       ┌── 7
│   ┌── 3
│   │   └── 6
│   │        
└── 1
    │       
    │   ┌── 5
    │   │   └── 10
    └── 2   ┌── 9
        └── 4
            └── 8

注：节点数值仅为循环生成的标识，核心要求是按层从左到右的顺序插入以保持树平衡，与数值大小无关。

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