高效合并两棵二叉搜索树并生成有序列表

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

def inorder_list(theroot):
    """
    对BST进行中序遍历，返回一个包含所有节点值的有序列表。
    时间复杂度: O(K)，其中K是BST的节点数量。
    """
    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:
    def merge(self, root1, root2):
        # 步骤1: 获取两棵BST的有序节点列表
        root1_list = inorder_list(root1)
        root2_list = inorder_list(root2)
        # 步骤2: 合并这两个有序列表
        return merge_two_sorted_lists(root1_list, root2_list)

import collections

class SolutionOptimized1:
    def merge(self, root1, root2):
        data = []
        def inorder(root):
            if root:
                inorder(root.left)
                data.append(root.data)
                inorder(root.right)

        # 收集root1的所有节点值
        inorder(root1)
        list1_sorted = list(data) # 复制一份，或者直接清空data再收集root2
        data.clear() # 清空data以便收集root2

        # 收集root2的所有节点值
        inorder(root2)
        list2_sorted = list(data)

        # 直接合并两个已排序的列表并排序
        return sorted(list1_sorted + list2_sorted)

import heapq

class SolutionOptimized2:
    def merge(self, root1, root2):
        list1_sorted = inorder_list(root1) # 沿用之前的inorder_list函数
        list2_sorted = inorder_list(root2)

        # 使用heapq.merge合并两个有序列表
        return list(heapq.merge(list1_sorted, list2_sorted))

import collections

class SolutionOptimized3:
    def merge(self, root1, root2):
        list1_sorted = inorder_list(root1)
        list2_sorted = inorder_list(root2)

        deque1 = collections.deque(list1_sorted)
        deque2 = collections.deque(list2_sorted)

        res = []
        while deque1 and deque2:
            if deque1[0] <= deque2[0]:
                res.append(deque1.popleft())
            else:
                res.append(deque2.popleft())

        res.extend(deque1) # 添加剩余元素
        res.extend(deque2)
        return res

class SolutionFinal:
    def merge(self, root1, root2):
        data = [] # 用于收集所有节点值的列表

        def inorder(root):
            """
            辅助函数：对BST进行中序遍历，并将节点值添加到外部的data列表中。
            """
            if root:
                inorder(root.left)
                data.append(root.data)
                inorder(root.right)

        # 对第一棵BST进行中序遍历，收集所有节点值
        inorder(root1)
        # 对第二棵BST进行中序遍历，继续收集所有节点值
        inorder(root2)

        # 对收集到的所有节点值进行排序
        # Timsort在此处能识别出data中包含两个已排序的子序列（来自root1和root2），
        # 并高效地将它们合并，达到O(M+N)的时间复杂度。
        data.sort() 
        return data