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

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

示例 1：

img

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

示例 2：

img

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

提示：

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

题解：

因为是二叉搜索树，性质为中序遍历后结果为有序，只需得到两棵树的中序遍历集合然后合并进行排序即可。

注：排序最好自己写，也可偷懒调用现成的api。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
    //结果数组
    ArrayList<Integer> res = new ArrayList<>();
    //中序遍历两棵树
    inorderTraversal(root1,res);
    inorderTraversal(root2,res);
    //排序
    Collections.sort(res);
    return res;

}

public void inorderTraversal(TreeNode root,List res){
    if (root == null){
        return;
    }

    inorderTraversal(root.left,res);
    res.add(root.val);
    inorderTraversal(root.right,res);
}
  • 时间复杂度：O(M + N)，M和N分别代表两颗搜索树的节点个数。
  • 空间复杂度：O(M + N)