如何基于已知大小的有序数组单遍构建平衡二叉搜索树（非自平衡树）？

首先明确结论：不存在时间复杂度为O(log n)的实现方案——构建包含n个节点的二叉搜索树，必须处理数组中的每一个元素，这一步的时间复杂度下限为O(n)，无法突破到O(log n)量级。

针对你的核心需求（单遍顺序遍历有序数组、仅支持高效顺序访问、不使用自平衡树），可以通过以下方案实现：

可行方案：基于完全二叉树结构构建近似平衡BST #

利用有序数组的中序遍历结果即为自身的特性，结合已知的数组总大小，预计算完全二叉树的子树节点数量，再通过顺序遍历数组填充节点值，最终构建出一棵近似平衡的BST（高度为O(log n)），无需自平衡树的旋转操作。

关键步骤：

1. 计算子树节点数：根据总节点数n，计算根节点左子树的节点数量，以此确定树的结构（保证是完全二叉树，避免退化为链表）。
2. 递归/迭代构建树：先构建左子树，再取当前数组的下一个元素作为根节点值，最后构建右子树，整个过程仅需单遍顺序遍历数组。

伪代码示例：

// 计算完全二叉树左子树的节点数
function getLeftSubtreeSize(totalNodes):
    treeHeight = floor(log2(totalNodes + 1))
    fullTreeSize = 2^treeHeight - 1
    lastLevelNodes = totalNodes - fullTreeSize
    if lastLevelNodes >= 2^(treeHeight - 1):
        return (2^(treeHeight - 1) - 1) + lastLevelNodes
    else:
        return 2^(treeHeight - 1) - 1

// 递归式构建（也可改用迭代实现）
function buildBST(orderedArray, totalNodes):
    if totalNodes == 0:
        return null
    
    leftSize = getLeftSubtreeSize(totalNodes)
    root = new TreeNode()
    
    // 先构建左子树，消耗leftSize个元素
    root.left = buildBST(orderedArray, leftSize)
    // 顺序取数组下一个元素作为根值
    root.value = orderedArray.next()
    // 构建右子树，消耗剩余节点
    root.right = buildBST(orderedArray, totalNodes - leftSize - 1)
    
    return root

复杂度说明：

• 时间复杂度：O(n)，每个元素仅被访问一次；
• 空间复杂度：O(log n)，递归栈（或迭代用的栈）深度为树的高度，完全二叉树高度为O(log n)。

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