题目

题目来源：力扣（LeetCode）

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

示例 1：

image.png

输入：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：

image.png

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

思路分析

二叉搜索树的一个特性是：中序遍历后返回的是一个有序序列。我们可以对两棵树分别进行中序遍历，得到数组 v1 和 v2，它们分别存放了两棵树中的所有元素，且均已有序。在这之后，我们通过归并排序的方法对 v1 和 v2 进行排序，就可以得到最终的结果。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val) {
  4.  *     this.val = val;
  5.  *     this.left = this.right = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {TreeNode} root1
  10.  * @param {TreeNode} root2
  11.  * @return {number[]}
  12.  */
  14. var getAllElements = function (root1, root2) {
  15.   let temp = [];//结果数组
  16.   //lnums从第一棵树中中序遍历出来的有序序列；rnums从第一棵树中中序遍历出来的有序序列
  17.   let lnums = [], rnums = [];
  18.   // 分别中序遍历两棵树
  19.   getNum(root1, lnums);
  20.   getNum(root2, rnums);
  21.   let p1 = 0, p2 = 0;//两个指针
  22.   // 当前还有元素没有被合并进去的结果数组的时候
  23.   while (p1 < lnums.length || p2 < rnums.length) {
  24.     // 这个时候判断，什么时候把左边放进去，什么时候把右边的放进去
  25.     // 当右边为空 或者 左边还有元素并且
  26.     if ((p2 >= rnums.length) || (p1 < lnums.length && lnums[p1] < rnums[p2])) {
  27.       temp.push(lnums[p1++]);
  28.     } else {
  29.       temp.push(rnums[p2++])//右边元素放到结果数组的末尾
  30.     }
  31.   }
  32.   return temp;
  33. };
  34. // 这里来实现中序遍历的过程
  35. var getNum = function (root, nums) {//传两个值，一个是树的根节点地址，一个是结果数组
  36.   if (root == null) return;//当前节点为空
  37.   getNum(root.left, nums);//先中序遍历左子树
  38.   nums.push(root.val);//将当前节点的值放到结果数组的后一位
  39.   getNum(root.right, nums);//中序遍历右子树
  40.   return;
  41. }