以尽可能低的时间复杂度合并两个二叉搜索树

Question

我目前正在解决一个问题，即完成一个函数来合并两个二叉搜索树并返回一个由两棵树的所有节点值组成的排序数组。

我已经写了一个可以正常工作的代码，但问题是它的时间复杂度似乎不够低。

时间复杂度应该是 O(M+N)，其中 M 和 N 是两个二叉搜索树的大小

期望的辅助空间应该是O(BST1的高度+BST2的高度+M+N(用于存储答案))

这是我写的代码

class Node:
    def __init__(self, data):
        self.left = None
        self.data = data
        self.right = None

def inorder_list(theroot):
    l = []
    def inorder(root):
        if root:
            inorder(root.left)
            l.append(root.data)
            inorder(root.right)
    inorder(theroot)
    return l

def merge_two_sorted_lists(list1, list2):
    res = []
    while list1 and list2:
        if list1[0] <= list2[0]:
            res.append(list1.pop(0))
        else:
            res.append(list2.pop(0))
    res += list1
    res += list2
    return res

class Solution:
    
    #Function to return a list of integers denoting the node 
    #values of both the BST in a sorted order.
    def merge(self, root1, root2):
        #code here.
        root1_list = inorder_list(root1)
        root2_list = inorder_list(root2)
        return merge_two_sorted_lists(root1_list, root2_list)

函数 inorder_list 返回一个由列表中所有节点值组成的列表（由于其中序遍历而排序）

函数 merge_two_sorted_lists 合并两个排序列表并返回一个由两个列表的所有元素组成的排序列表。

每个中序遍历函数的时间复杂度为 O(bst 的大小)，merge_*two_*sorted_lists 的时间复杂度为第一个列表的大小 + 第二个列表的大小 (M+N)。

我的想法是创建一个空堆栈并在同时遍历两个 BTS 时填充它，但我不知道该怎么做。

还有其他时间复杂度为 O(M+N) 的算法吗？

Answer 1

您的合并不是 O(M+N)，因为成本高昂

pop(0)

。只要做

return sorted(list1 + list2)

。