网络异常，图片无法展示
|
给你 root1 和 root2 这两棵二叉搜索树。
请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.
示例 1：
网络异常，图片无法展示
|
输入： root1 = [2,1,4], root2 = [1,0,3] 输出： [0,1,1,2,3,4] 复制代码
示例 2：
输入： root1 = [0,-10,10], root2 = [5,1,7,0,2] 输出： [-10,0,0,1,2,5,7,10] 复制代码
示例 3：
输入： root1 = [], root2 = [5,1,7,0,2] 输出： [0,1,2,5,7] 复制代码
示例 4：
输入： root1 = [0,-10,10], root2 = [] 输出： [-10,0,10] 复制代码
示例 5：
网络异常，图片无法展示
|
输入： root1 = [1,null,8], root2 = [8,1] 输出： [1,1,8,8] 复制代码
提示：
- 每棵树最多有
5000个节点。 - 每个节点的值在
[-10^5, 10^5]之间。
sort 排序
解题思路
遍历两棵二叉搜索树，将节点值插入数组。
对节点值数组进行升序排序，返回排序后的结果数组即可。时间复杂度为 O(n log n)。
代码实现
var getAllElements = function(root1, root2) { // 创建节点值数组 const arr = []; // 中序遍历 function inorder(node){ if(node === null) return; inorder(node.left); // 将每个节点值插入数组 arr.push(node.val); inorder(node.right); } inorder(root1); inorder(root2); // 将数组进行升序排序并返回 return arr.sort((a,b) => a-b) }; 复制代码
归并排序
解题思路
因为二叉搜索树的性质为左子树的节点值都小于根节点值，右子树的节点值都大于根节点值。所以如果对二叉搜索树进行中序遍历，得到的结果数组是一个升序的数组。
我们可以基于这样的一个结果，进行归并排序，这样的排序时间复杂度为 O(n)。所以相对于之前的 sort 排序解题，时间复杂度上会有一个优化。
代码实现
var getAllElements = function(root1, root2) { // 创建两个数组，分别保存两棵树的节点值 const arr1 = [],arr2 = []; function inorder(node,arr){ if(node === null) return; inorder(node.left,arr); arr.push(node.val); inorder(node.right,arr); } inorder(root1,arr1); inorder(root2,arr2); // 创建结果数组 const res = [], // 对两个有序数组进行归并排序 len1 = arr1.length,len2 = arr2.length; let i = 0,j = 0; while(i<len1 || j<len2){ if(j===len2 || (i<len1 && (arr1[i]<arr2[j]))){ res.push(arr1[i]); i++ }else{ res.push(arr2[j]) j++ } } // 返回排序后的结果 return res; }; 复制代码
至此我们就完成了 leetcode-1305-两棵二叉搜索树中的所有元素
如有任何问题或建议，欢迎留言讨论！
