关键词：力扣，LeetCode，题解，清晰讲解，算法，二叉树，二叉搜索树，合并，Python
题目地址：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 上也有相关题目：
# 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
复杂度
- 时间复杂度：O(M+N)
- 空间复杂度：O(M+N)
总结
1、 本题考察了三个知识点：BST的性质、中序遍历、合并两个有序数组都是基础问题，可见基础知识的重要性，一通百通；
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发