1305. All Elements in Two Binary Search Trees 两棵二叉搜索树中的所有元素

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/ 关键词：力扣，LeetCode，题解，清晰讲解，算法，二叉树，二叉搜索树，合并，Python

---

@TOC

题目地址：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees/

题目描述

给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.

 

示例 1：

输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[0,1,1,2,3,4]

示例 2：

输入：root1 = [1,null,8], root2 = [8,1]
输出：[1,1,8,8]

 

提示：

• 每棵树的节点数在 [0, 5000] 范围内
• -105 <= Node.val <= 105

题目大意

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

解题方法

方法一：中序遍历 + 归并

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

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

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

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

LeetCode 上也有相关题目：

• 88. 合并两个有序数组
• 21. 合并两个有序链表

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def getAllElements(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: List[int]
        """
        nums1 = []
        nums2 = []
        self.inOrder(root1, nums1)
        self.inOrder(root2, nums2)
        return self.merge(nums1, nums2)
        
        
    def inOrder(self, root, nums):
        if not root:
            return
        self.inOrder(root.left, nums)
        nums.append(root.val)
        self.inOrder(root.right, nums)
    
    def merge(self, nums1, nums2):
        res = []
        p1 = 0
        p2 = 0
        while p1 < len(nums1) and p2 < len(nums2):
            if nums1[p1] < nums2[p2]:
                res.append(nums1[p1])
                p1 += 1
            else:
                res.append(nums2[p2])
                p2 += 1
        if p1 < len(nums1):
            res.extend(nums1[p1:])
        if p2 < len(nums2):
            res.extend(nums2[p2:])
        return res

复杂度

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

总结

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

日期

2022 年 5 月 1 日—— 劳动人民的假日，从刷题开始！