如何将随机二叉搜索树的递归替换为循环？以insertRoot为例

先看标准的递归实现（带父指针），作为对比基准：

// 递归版insertRoot
public Node insertRoot(Node root, int val) {
    if (root == null) {
        return new Node(val);
    }
    // 50%概率选择左/右子树插入
    if (Math.random() < 0.5) {
        root.left = insertRoot(root.left, val);
        root.left.parent = root;
    } else {
        root.right = insertRoot(root.right, val);
        root.right.parent = root;
    }
    return root;
}

递归转循环的核心是模拟递归的深度遍历路径，用父指针追踪当前节点的上级，同时保留随机选择逻辑。以下是正确的循环实现：

// 循环版insertRoot
public Node insertRoot(Node root, int val) {
    Node newNode = new Node(val);
    // 边界处理：空树直接返回新节点
    if (root == null) {
        return newNode;
    }

    Node current = root;
    Node parent = null;
    // 循环遍历直到找到空的叶子位置
    while (true) {
        parent = current;
        // 每次循环都重新随机选择插入方向
        if (Math.random() < 0.5) {
            if (current.left == null) {
                current.left = newNode;
                newNode.parent = parent;
                break;
            } else {
                current = current.left;
            }
        } else {
            if (current.right == null) {
                current.right = newNode;
                newNode.parent = parent;
                break;
            } else {
                current = current.right;
            }
        }
    }
    return root;
}

常见错误（导致元素丢失的原因） #

• 错误1：随机逻辑只执行一次：比如在循环外只判断一次方向，导致所有插入都往同一个子树走，最终部分元素被覆盖或无法插入
• 错误2：未正确追踪父节点：挂载新节点时没有找到空的叶子位置，而是直接覆盖了已有子节点
• 错误3：忽略空树边界：首次插入时没有返回新节点，导致树始终为空

验证方法 #

用中序遍历检查所有元素是否存在：

public void inorderTraversal(Node root) {
    if (root == null) return;
    inorderTraversal(root.left);
    System.out.print(root.val + " ");
    inorderTraversal(root.right);
}

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