大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

把两棵二叉搜索树的所有元素，合并成有序的一个数组。

解题方法

思路：牢记二叉搜索树的中序遍历是有序的。

这句话，在我的每个关于二叉搜索树 (BST) 的题解都出现过，因为这是解决 BST 的关键。

因此，可以对两个二叉搜索树分别进行中序遍历，得到两个有序的数组。然后合并两个有序数组即可。

合并两个有序数组的代码，可以参考归并排序。

LeetCode 上也有相关题目：

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution(object):
  8.     def getAllElements(self, root1, root2):
  9.         """
  10.         :type root1: TreeNode
  11.         :type root2: TreeNode
  12.         :rtype: List[int]
  13.         """
  14.         nums1 = []
  15.         nums2 = []
  16.         self.inOrder(root1, nums1)
  17.         self.inOrder(root2, nums2)
  18.         return self.merge(nums1, nums2)
  21.     def inOrder(self, root, nums):
  22.         if not root:
  23.             return
  24.         self.inOrder(root.left, nums)
  25.         nums.append(root.val)
  26.         self.inOrder(root.right, nums)
  28.     def merge(self, nums1, nums2):
  29.         res = []
  30.         p1 = 0
  31.         p2 = 0
  32.         while p1 < len(nums1) and p2 < len(nums2):
  33.             if nums1[p1] < nums2[p2]:
  34.                 res.append(nums1[p1])
  35.                 p1 += 1
  36.             else:
  37.                 res.append(nums2[p2])
  38.                 p2 += 1
  39.         if p1 < len(nums1):
  40.             res.extend(nums1[p1:])
  41.         if p2 < len(nums2):
  42.             res.extend(nums2[p2:])
  43.         return res

复杂度

  • 时间复杂度：$O(M + N)$
  • 空间复杂度：$O(M + N)$

    总结

  1. 本题考察了三个知识点：BST 的性质、中序遍历、合并两个有序数组。都是基础问题，可见基础知识的重要性，一通百通。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。