如何将两棵二叉搜索树转换为指定复杂度的红黑树

阿华AIGC实验室

2026-5-15

解答：将两棵BST转换为红黑树（满足时间/空间复杂度要求）

要解决这个问题，我们需要结合BST的遍历特性和红黑树的线性构建方法，同时严格控制时间和空间开销。下面是分步实现的思路：

核心思路概述

我们的目标是避免额外存储整个有序序列（否则空间会达到Θ(m+n)，不符合要求），而是通过迭代中序遍历同时处理两棵BST，得到一个流式的有序元素序列，再基于这个序列线性构建红黑树。整个过程的时间复杂度为Θ(max(m,n))，空间复杂度为Θ(max(h1,h2))。

步骤1：迭代式合并两棵BST为有序流

两棵BST的中序遍历结果都是有序的，我们可以用两个栈来实现迭代中序遍历，同时比较两个遍历的当前节点，按升序逐个输出元素。这种方法不需要存储整个序列，栈的大小仅取决于两棵BST的高度，空间开销刚好是Θ(h1+h2)=Θ(max(h1,h2))。

具体实现逻辑：

初始化两个栈，分别将T1和T2的所有左子节点依次压入栈中（模拟中序遍历的左链遍历）。
每次比较两个栈顶节点的键值，取出较小的那个节点输出；然后将该节点的右子树的所有左节点压入对应栈中，继续遍历。
如果其中一个栈为空，则直接遍历另一个栈的剩余节点。

示例伪代码：

// 迭代中序遍历合并两棵BST，返回有序元素列表（实际可改为流式输出）
vector<int> mergeBSTs(TreeNode* t1, TreeNode* t2) {
    stack<TreeNode*> s1, s2;
    vector<int> result;
    
    // 初始化左链
    while (t1) { s1.push(t1); t1 = t1->left; }
    while (t2) { s2.push(t2); t2 = t2->left; }
    
    while (!s1.empty() || !s2.empty()) {
        // 选择当前较小的节点
        if (s2.empty() || (!s1.empty() && s1.top()->val <= s2.top()->val)) {
            TreeNode* node = s1.top(); s1.pop();
            result.push_back(node->val);
            // 处理右子树的左链
            node = node->right;
            while (node) { s1.push(node); node = node->left; }
        } else {
            TreeNode* node = s2.top(); s2.pop();
            result.push_back(node->val);
            node = node->right;
            while (node) { s2.push(node); node = node->left; }
        }
    }
    return result;
}

注：这里用vector存储结果只是为了演示，实际可以用迭代器直接流式输出，完全避免O(m+n)的额外空间占用。

步骤2：基于有序流线性构建红黑树

有了有序的元素流后，我们需要用线性时间构建红黑树。这里推荐使用**左倾红黑树（Left-Leaning Red-Black Tree）**的有序插入方法，因为对于有序元素，左倾红黑树的插入操作是均摊O(1)时间，总时间复杂度为Θ(m+n)。

左倾红黑树的有序插入逻辑（针对升序流）：

每次将新元素插入为当前树的最右节点。
按照左倾红黑树的规则进行旋转和颜色翻转，保持树的平衡和红黑性质：
- 如果右孩子是红色而左孩子是黑色，进行左旋转。
- 如果左孩子是红色且左孩子的左孩子也是红色，进行右旋转。
- 如果左右孩子都是红色，进行颜色翻转。

这种方法不需要递归，迭代实现的空间开销仅为O(log(m+n))，远小于Θ(max(h1,h2))（即使原BST是不平衡的，比如h1=m，log(m+n)也远小于m），完全符合空间要求。

复杂度验证

时间复杂度：迭代中序遍历是Θ(m+n)=Θ(max(m,n))，左倾红黑树的有序插入总时间是Θ(m+n)，所以整体时间复杂度为Θ(max(m,n))。
空间复杂度：迭代遍历的栈空间是Θ(max(h1,h2))，构建红黑树的迭代过程空间是O(log(m+n))，两者取最大值后仍为Θ(max(h1,h2))，符合要求。