能否将非平衡BST转换为红黑树，实现O(n)时间、O(h)空间复杂度？
当然可以！而且确实存在一套成熟的方法，能在O(n)时间和O(h)空间的限制下完成这个转换——核心思路是先把非平衡BST掰成完全平衡的二叉搜索树，再给节点按红黑树规则着色就行。
咱一步步拆解来看：
第一步：用中序遍历提取BST的有序序列（O(n)时间，O(h)空间）
非平衡BST的中序遍历结果本身就是升序的，这是BST的核心特性。这里不用额外开数组存整个序列（那样会占O(n)空间），而是用递归的中序遍历，利用递归栈的O(h)空间（h是原BST的高度），同时配合后续的分治构建，边遍历边构建平衡树。
如果担心递归栈溢出，也可以用迭代版的中序遍历，空间同样是O(h)。
第二步：分治构建平衡二叉搜索树（O(n)时间，O(h)空间）
我们先统计出原BST的总节点数n，然后用分治法递归构建：
- 取序列的中间节点作为当前子树的根（保证左右子树大小差不超过1，天然平衡）
- 递归构建左子树（对应序列的前半段）
- 递归构建右子树（对应序列的后半段）
这个过程里，递归栈的深度最多是平衡树的高度（也就是O(logn)），但因为原BST的高度是h，递归栈深度不会超过h，所以空间还是O(h)。整个构建过程每个节点只被访问一次，时间是O(n)。
第三步：给平衡BST着色为红黑树（O(n)时间，O(h)空间）
平衡BST的结构已经满足红黑树的“高度平衡”要求（红黑树的高度最多是2log(n+1)），现在只需要给节点着色，满足红黑树的四条规则：
- 根节点是黑色
- 所有NIL叶子节点是黑色
- 红色节点的两个子节点必须是黑色
- 从根到任意NIL叶子的路径上，黑色节点的数量相同
针对平衡BST，我们可以用一个简单的着色策略：
- 根节点设为黑色
- 对每个节点，如果它的父节点是黑色，就把它设为红色；如果父节点是红色，就设为黑色（也就是父子节点颜色交替）
这种着色方式天然满足所有规则：没有连续的红色节点，每条路径的黑色节点数完全一致，完美符合红黑树的要求。着色过程可以用递归或者迭代，时间O(n)，空间O(h)（递归栈）。
为什么空间是O(h)而不是O(n)？
关键在于我们没有额外存储整个有序序列，而是把中序遍历和平衡树构建结合起来了——在递归构建左子树的时候，同步完成中序遍历的左半部分，不需要把所有节点提前存下来，只靠递归栈的O(h)空间就能推进整个流程。
总结
完全可以将大小为n、高度为h的非平衡BST转换为红黑树，且满足时间复杂度O(n)、空间复杂度O(h)的要求，核心就是“中序遍历+分治平衡构建+交替着色”的组合拳。
内容的提问来源于stack exchange，提问作者Tal
