构建平衡二叉树：非BST的左到右插入策略

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

// 假设 TreeNode 是一个包含 int data 和 TreeNode left/right 的类
class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

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

    // 初始尝试的插入方法
    TreeNode insert(int data, TreeNode root, boolean isLeft){
        if(root == null){
            return new TreeNode(data); // 如果根为空，创建新根
        }
        else if(root.left == null){
            root.left = new TreeNode(data);
        }
        else if(root.right == null){
            root.right = new TreeNode(data);
        }
        else{
            // 尝试通过 isLeft 标志递归向下
            if(isLeft){
                insert(data, root.right, false); // 这里的递归调用没有更新 root.right
            }
            else{
                insert(data, root.left, true); // 这里的递归调用没有更新 root.left
            }
        }
        return root;
    }
}

      1
     / \
    2   3
   / \ / \
  4  5 6  7

// TreeNode.java
public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

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

    // toString 方法用于打印树结构，这里省略具体实现，
    // 假定它能生成类似问题描述中的可视化输出。
    @Override
    public String toString() {
        return "TreeNode{" +
               "data=" + data +
               ", left=" + (left != null ? left.data : "null") +
               ", right=" + (right != null ? right.data : "null") +
               '}';
    }

    // 核心插入方法
    public TreeNode insert(int data, int size) {
        // 如果当前节点是 null，这通常意味着是第一次插入，
        // 但此方法预期在非空根节点上调用，所以此情况应在外部处理或作为特殊情况。
        // 这里假设 'this' 总是有效的根节点。

        TreeNode currentNode = this; // 从当前节点（通常是根）开始遍历

        // 获取 (size + 1) 的二进制表示。
        // (size + 1) 是下一个要插入节点的逻辑索引。
        // >> 1 移除最低位，然后 substring(1) 移除最高位。
        // 这样剩下的二进制字符串就是从根节点到新节点父节点的路径。
        // 例如：size=4, size+1=5 (101)。 (5>>1)=2 (10)。 "10".substring(1) -> "0"。
        // 路径 "0" 意味着从根向左走一步。
        String bits = Integer.toBinaryString((size + 1) >> 1).substring(1);

        // 遍历路径位，找到新节点的父节点
        for (char bit : bits.toCharArray()) {
            if (bit == '1') { // '1' 表示向右
                currentNode = currentNode.right;
            } else { // '0' 表示向左
                currentNode = currentNode.left;
            }
        }

        // 此时 currentNode 是新节点的父节点
        // 根据完全二叉树的填充规则，如果父节点的左子节点为空，则插入到左侧；
        // 否则，插入到右侧。这对应于 (size + 1) 的最低位。
        if (currentNode.left == null) {
            currentNode.left = new TreeNode(data);
        } else {
            currentNode.right = new TreeNode(data);
        }
        return this; // 返回根节点（通常是调用方法的对象本身）
    }
}