如何在指定复杂度下从两棵BST合并构建红黑树？

步骤1：将BST转为有序双向链表 #

用迭代中序遍历处理两棵BST，直接修改原节点的left/right指针，把树结构转为有序双向链表：

• 遍历过程用栈存储待访问节点，空间复杂度为对应树高θ(h1)、θ(h2)，符合要求。
• 遍历完成后得到两个升序的双向链表L1（对应T1的中序序列）和L2（对应T2的中序序列），时间复杂度θ(n1)+θ(n2)=θ(max(n1,n2))。
• 全程复用原节点，无额外节点创建。

步骤2：合并两个有序双向链表 #

参照归并排序的合并逻辑，用指针遍历L1和L2，每次选取当前key更小的节点接入结果链表，直到其中一个链表遍历完毕，再将剩余节点直接追加到结果末尾：

• 仅使用常数级指针变量，空间复杂度θ(1)。
• 时间复杂度θ(n1+n2)=θ(max(n1,n2))。

步骤3：将有序双向链表转为红黑树 #

利用有序序列线性构建红黑树，核心思路是先构建平衡结构，再调整颜色符合红黑树性质：

1. 构建完全二叉树结构：以链表中间节点为根，用迭代方式将左右子链表分别构建为左右子树——完全二叉树的结构天然接近红黑树的平衡要求，构建过程时间θ(n)，空间复杂度θ(logn)（远小于题目允许的θ(max(h1,h2))）。
2. 调整颜色与修正性质：
   • 初始所有节点为红色，先将根节点设为黑色。
   • 从最底层向上遍历，检查每个红色节点的父节点：若父节点也是红色，则根据叔父节点的颜色进行旋转（左旋/右旋）或颜色翻转，修复“红节点不可相邻”规则。
   • 同步确保所有从根到叶子的路径上黑色节点数量一致，必要时调整子树的黑色高度。

• 这一步总时间复杂度为θ(n)，每个节点最多被访问常数次。

关键约束满足验证 #

• 复用节点：所有操作仅修改原节点的指针和颜色属性，无新节点分配。
• 时间复杂度：三步均为线性时间，总复杂度θ(max(n1,n2))。
• 空间复杂度：迭代中序遍历的栈空间为θ(max(h1,h2))，后续步骤空间均不超过该值，符合要求。

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