合并两个二叉搜索树并实现O(M+N)时间复杂度的优化咨询

嗨，你的思路方向其实是对的——利用BST的中序遍历是有序序列的特性，再合并两个有序列表，问题出在你实现合并的方式上，导致时间复杂度没达标。让我一步步帮你分析和优化：

首先分析现有代码的瓶颈：
你的merge_two_sorted_lists函数里用了list1.pop(0)和list2.pop(0)，但Python的列表是动态数组结构，删除第一个元素的时间复杂度是O(k)（k是当前列表的长度），因为要把后面所有元素往前移一位。这样合并两个长度为M和N的列表时，总时间会变成O(M*N)，直接打破了O(M+N)的时间要求。

优化方案1：修复合并函数，用双指针实现O(M+N)合并 #

只需要把合并逻辑改成双指针遍历，避免修改原列表（用索引移动代替pop操作），就能把合并的时间降到O(M+N)。修改后的合并函数如下：

def merge_two_sorted_lists(list1, list2):
    res = []
    i = j = 0
    len1, len2 = len(list1), len(list2)
    while i < len1 and j < len2:
        if list1[i] <= list2[j]:
            res.append(list1[i])
            i += 1
        else:
            res.append(list2[j])
            j += 1
    # 把剩余的元素直接追加
    res.extend(list1[i:])
    res.extend(list2[j:])
    return res

这样修改后，你的整体代码时间复杂度就是O(M+N)了：两次中序遍历各O(M)和O(N)，合并O(M+N)，完全符合要求。

优化方案2：迭代式中序遍历+边遍历边合并（更优的空间利用） #

你提到的用栈同时遍历两个BST的思路非常好，这种方法不需要先把两个树的所有元素都存储到两个列表里，栈的空间只需要O(Height of BST1 + Height of BST2)，再加上存储结果的O(M+N)，完全符合题目要求的辅助空间限制，时间复杂度依然是O(M+N)。

实现思路是模拟递归中序遍历的栈操作，同时维护两个BST的遍历栈，每次取出两个栈顶节点中值较小的那个，加入结果列表，然后继续遍历它的右子树（按照中序遍历的顺序）。具体代码如下：

class Solution:
    def merge(self, root1, root2):
        stack1, stack2 = [], []
        res = []
        curr1, curr2 = root1, root2
        
        # 先把两个树的左链都压入栈（初始化中序遍历的准备）
        while curr1:
            stack1.append(curr1)
            curr1 = curr1.left
        while curr2:
            stack2.append(curr2)
            curr2 = curr2.left
        
        while stack1 or stack2:
            # 选择栈顶值较小的那个树进行遍历
            if not stack2 or (stack1 and stack1[-1].data <= stack2[-1].data):
                node = stack1.pop()
                res.append(node.data)
                # 处理当前节点的右子树，把右子树的左链压入栈
                curr = node.right
                while curr:
                    stack1.append(curr)
                    curr = curr.left
            else:
                node = stack2.pop()
                res.append(node.data)
                curr = node.right
                while curr:
                    stack2.append(curr)
                    curr = curr.left
        
        return res

这个方法的优势在于：

• 不需要预先存储两个完整的中序列表，节省了额外的O(M+N)临时空间（除了结果列表）
• 栈的空间只取决于两个BST的高度，对于平衡BST来说，高度是logM和logN，空间效率很高

总结一下：

• 如果只是想快速修复现有代码，优化合并函数的双指针版本就足够了
• 如果想达到题目要求的最优辅助空间，就用迭代式中序遍历+边遍历边合并的方法

备注：内容来源于stack exchange，提问作者Mohammad