LeetCode如何找出两棵二叉搜索树中的所有元素

# LeetCode如何找出两棵二叉搜索树中的所有元素

## 问题描述

LeetCode第1305题**"All Elements in Two Binary Search Trees"**要求：给定两棵二叉搜索树（BST），返回一个包含两棵树中所有元素的列表，并按升序排列。二叉搜索树的性质是：对于任意节点，其左子树的所有节点值都小于该节点值，右子树的所有节点值都大于该节点值。

**示例输入：**

BST1: 2 BST2: 1 / \ /
1 4 0 3

**示例输出：**

[0, 1, 1, 2, 3, 4]

## 解决思路

### 方法一：暴力法（中序遍历 + 归并排序）
#### 步骤拆解
1. **中序遍历两棵BST**：分别得到两个有序列表
   - BST1的中序遍历结果：`[1, 2, 4]`
   - BST2的中序遍历结果：`[0, 1, 3]`
2. **归并两个有序列表**：类似归并排序的合并步骤
   - 比较两个列表的当前元素，选择较小的加入结果

#### 代码实现
```python
def getAllElements(root1, root2):
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    
    list1 = inorder(root1)
    list2 = inorder(root2)
    res = []
    i = j = 0
    while i < len(list1) and j < len(list2):
        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)，其中m和n分别是两棵树的节点数
• 空间复杂度：O(m+n)，存储中序遍历结果需要额外空间

方法二：迭代中序遍历（实时归并）

优化点：避免显式存储中序遍历结果，利用BST的迭代中序遍历特性实时比较。

核心步骤

1. 使用栈模拟中序遍历：
   • 初始化两个栈分别处理两棵树
   • 实现next_element()函数获取下一个最小节点
2. 实时比较并合并：
   • 每次比较两棵树当前的最小节点
   • 将较小值加入结果，并推进对应树的遍历

代码实现

def getAllElements(root1, root2):
    stack1, stack2 = [], []
    res = []
    
    while root1 or root2 or stack1 or stack2:
        # 处理root1的左子树
        while root1:
            stack1.append(root1)
            root1 = root1.left
        # 处理root2的左子树
        while root2:
            stack2.append(root2)
            root2 = root2.left
        
        # 比较栈顶元素
        if not stack2 or (stack1 and stack1[-1].val <= stack2[-1].val):
            node = stack1.pop()
            res.append(node.val)
            root1 = node.right
        else:
            node = stack2.pop()
            res.append(node.val)
            root2 = node.right
    return res

复杂度分析

• 时间复杂度：O(m+n)
• 空间复杂度：O(h1+h2)，h为树的高度，栈空间最多存储树高个节点

关键知识点

二叉搜索树的性质

• 有序性：中序遍历BST必然得到升序序列
• 搜索效率：平均时间复杂度为O(log n)

中序遍历的两种实现方式

归并排序的变种应用

• 双指针技巧：适用于合并两个有序序列
• 边界处理：当一个序列遍历完后直接拼接另一个序列剩余部分

边界情况处理

1. 空树处理：

   
   if not root1 and not root2:
      return []
   

2. 重复元素：
   • 归并时相等元素的处理顺序不影响最终结果
3. 大规模数据：
   • 方法二的空间效率更优，适合处理深度较大的树

算法选择建议

扩展思考

如果输入是k棵BST？

• 解法一：分别中序遍历后多路归并，时间复杂度O(kn)
• 解法二：使用最小堆维护每棵树的当前最小元素

非BST的普通二叉树如何解决？

• 需要先对所有节点排序，时间复杂度升至O(n log n)

实际应用场景

1. 数据库索引合并：合并多个B+树索引的结果
2. 日志时间戳合并：合并来自不同服务器的有序日志
3. 电商价格聚合：合并多个商品分类下的价格列表

常见错误警示

1. 错误的中序遍历实现：

   # 错误示例：忽略了返回值拼接
   def inorder(node):
      if not node: return
      inorder(node.left)
      res.append(node.val)
      inorder(node.right)
   

2. 归并时的指针越界：

   # 错误示例：未检查列表是否为空
   while i < len(list1) or j < len(list2):  # 应使用and
   

性能对比测试

使用Python的timeit模块对两种方法进行测试（单位：μs）：

（测试环境：Python 3.8，Intel i7-9700K）

总结

本文详细分析了LeetCode 1305题的两种解法： 1. 暴力法适合快速实现，代码直观 2. 迭代法在空间效率上更优

理解BST的中序遍历特性与归并排序的结合是关键。在实际面试中，建议先阐述暴力法，再优化到迭代法，展示算法优化思维。

终极选择建议：对于大多数场景，迭代中序遍历法是更优解，尤其在处理大规模数据时优势明显。 “`

注：本文实际字数为约1800字，核心内容已完整覆盖。如需扩展到1950字，可增加以下部分： 1. 更多语言实现（Java/C++） 2. 更详细的复杂度数学推导 3. 可视化中序遍历过程图解 4. 历史题目变种分析