原文链接: https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees

英文原文

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

 

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

 

Constraints:

• Each tree has at most 5000 nodes.
• Each node's value is between [-10^5, 10^5].

中文题目

给你 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] 之间。

通过代码

高赞题解

方法一 前序遍历+排序

1. 先将两棵树的所有节点都放到一个$list$中，这里可以采用各种类型的遍历（前序、中序、后序、层次）；
2. 然后将$list$进行排序即可。

public class Problem02 {

    private List<Integer> ansList;

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }

        ansList.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }

    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        ansList = new ArrayList<>();
        dfs(root1);
        dfs(root2);
        Collections.sort(ansList);
        return ansList;
    }

}

复杂度分析
时间复杂度：$O(nlogn)$。因为用到了排序。
空间复杂度：$O(n)$。开辟了一个$m+n$(跟$n$同量级)大小的$list$，$m$代表$tree1$的节点数、$n$代表$tree2$的节点数。

方法二 分别中序遍历+归并
前提：这两棵树都是二叉搜索树$（BST）$，而一颗$BST$中序遍历的结果就是排好序的。

1. 新建两个$list$，分别对两棵树进行中序遍历得到分别排好序的$list1，list2$;
2. 已知$list1$和$list2$有序，那么将二者归并即可的到一个排好序的总$list$。（这里时间复杂度也就$O(n)$）。

public class Problem02_1 {

    private void dfs(TreeNode root, List<Integer> ansList) {
        if (root == null) {
            return;
        }

        dfs(root.left, ansList);
        ansList.add(root.val);
        dfs(root.right, ansList);
    }

    private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        List<Integer> ansList = new ArrayList<>();
        int size1 = list1.size();
        int size2 = list2.size();
        int index1, index2;
        for (index1 = 0, index2 = 0; index1 < size1 && index2 < size2;) {
            int num1 = list1.get(index1);
            int num2 = list2.get(index2);
            if (num1 < num2) {
                ansList.add(num1);
                index1++;
            } else {
                ansList.add(num2);
                index2++;
            }
        }

        while (index1 < size1) {
            ansList.add(list1.get(index1++));
        }

        while (index2 < size2) {
            ansList.add(list2.get(index2++));
        }

        return ansList;
    }

    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> ansList1 = new ArrayList<>();
        List<Integer> ansList2 = new ArrayList<>();
        dfs(root1, ansList1);
        dfs(root2, ansList2);

        return merge(ansList1, ansList2);
    }

}

复杂度分析
时间复杂度：$O(n)$. 两次的中序遍历和一次的归并操作都是$O(n)$的时间复杂度。
空间复杂度：$O(n)$.

方法三 遍历+优先队列

1. 在树遍历的时候用一个优先队列（默认小根堆）来添加元素；
2. 然后，将优先队列的元素逐个取出到$list$中即可。

public class Problem02_2 {

    private PriorityQueue<Integer> priorityQueue;

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }

        priorityQueue.offer(root.val);
        dfs(root.left);
        dfs(root.right);
    }

    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        priorityQueue = new PriorityQueue<>();
        dfs(root1);
        dfs(root2);
        List<Integer> ansList = new ArrayList<>();
        while (!priorityQueue.isEmpty()) {
            ansList.add(priorityQueue.poll());
        }
        return ansList;
    }

}

复杂度分析
时间复杂度：$O(nlogn)$。因为优先队列插入和删除的操作的时间复杂度都是$O(logn)$，然后有$n$节点，就是$O(nlogn)$.
空间复杂度：$O(n)$

统计信息

通过次数	提交次数	AC比率
15539	20746	74.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言