题目内容

给你 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] 范围内
• -10⁵ <= Node.val <= 10⁵

解题思路

对两颗二叉搜索树中序遍历，把两个中序遍历结果合并。

public class Solution {

   public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
       List<Integer> d1 = new ArrayList<>();
       List<Integer> d2 = new ArrayList<>();
       inorderTraversal(root1, d1);
       inorderTraversal(root2, d2);

       List<Integer> list = new ArrayList<>();
       int l1 = d1.size(), l2 = d2.size(), i = 0, j = 0;
       while (i < l1 || j < l2) {
           int a = i < l1 ? d1.get(i) : Integer.MAX_VALUE, b = j < l2 ? d2.get(j) : Integer.MAX_VALUE;

           if (a < b) {
               list.add(a);
               i++;
           } else {
               list.add(b);
               j++;
           }
       }

       return list;
   }

   private void inorderTraversal(TreeNode node, List<Integer> deque) {
       if (node == null) return;
       inorderTraversal(node.left, deque);
       deque.add(node.val);
       inorderTraversal(node.right, deque);
   }
}


class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;

   TreeNode() {
   }

   TreeNode(int val) {
       this.val = val;
   }

   TreeNode(int val, TreeNode left, TreeNode right) {
       this.val = val;
       this.left = left;
       this.right = right;
   }
}

运行结果