题目

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

示例 1： image.png

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

示例 2： image.png

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

最直接的办法就是分别中序遍历两棵树存储到两个list中，然后合并两个有序的list。

代码

  1. class Solution {
  2.     public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
  3.         List<Integer> nums1 = new ArrayList<>();
  4.         List<Integer> nums2 = new ArrayList<>();
  5.         inorder(root1, nums1);
  6.         inorder(root2, nums2);
  8.         List<Integer> ans = new ArrayList<>();
  9.         int p = 0;
  10.         int q = 0;
  11.         int m = nums1.size();
  12.         int n = nums2.size();
  13.         while (p < m || q < n) {
  14.             if (p == m) {
  15.                 ans.add(nums2.get(q++));
  16.             } else if (q == n) {
  17.                 ans.add(nums1.get(p++));
  18.             } else if (nums1.get(p) < nums2.get(q)) {
  19.                 ans.add(nums1.get(p++));
  20.             } else {
  21.                 ans.add(nums2.get(q++));
  22.             }
  23.         }
  24.         return ans;
  25.     }
  27.     public void inorder(TreeNode node, List<Integer> res) {
  28.         if (node == null) {
  29.             return;
  30.         }
  31.         inorder(node.left, res);
  32.         res.add(node.val);
  33.         inorder(node.right, res);
  34.     }
  35. }