1305. 两棵二叉搜索树中的所有元素

题目描述

给你 root1 和 root2 这两棵二叉搜索树。

请你返回一个列表，其中包含 两棵树 中的所有整数并按升序排序。

示例:略。

提示:略。

来源：LeetCode

思路

先中序遍历两棵树，得到两个有序数组。再用归并排序中的合并有序数组合并起来即可。

解法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

// 中序遍历
const inOrder = root => {
  if (!root) return [];

  return [...inOrder(root.left), root.val, ...inOrder(root.right)];
};

// 归并排序中的合并有序数组
const merge = (array1, array2) => {
  const result = [];

  let i = 0;
  let j = 0;

  while (i < array1.length && j < array2.length) {
    if (array1[i] < array2[j]) {
      result.push(array1[i]);
      i++;
    } else {
      result.push(array2[j]);
      j++;
    }
  }

  if (i < array1.length) {
    result.push(...array1.slice(i));
  }

  if (j < array2.length) {
    result.push(...array2.slice(j));
  }

  return result;
};

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {number[]}
 */
const getAllElements = (root1, root2) => {
  const array1 = inOrder(root1);
  const array2 = inOrder(root2);

  return merge(array1, array2);
};