网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 1305. 两棵二叉搜索树中的所有元素 ，难度为 中等。
Tag : 「中序遍历」、「归并排序」
给你 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][0,5000] 范围内
- -10^5 <= Node.val <= 10^5−105<=Node.val<=105
中序遍历 + 归并排序
利用 BST 中序遍历的有序性质，我们可以先对两棵树进行中序遍历，从而将树的结构转换为线性结构。
将两个有序序列合并成一个有序序列则是利用了经典的「归并排序」。
代码：
class Solution { int INF = 0x3f3f3f3f; public List<Integer> getAllElements(TreeNode root1, TreeNode root2) { List<Integer> ans = new ArrayList<>(); List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>(); dfs(root1, l1); dfs(root2, l2); int n = l1.size(), m = l2.size(), i = 0, j = 0; while (i < n || j < m) { int a = i < n ? l1.get(i) : INF, b = j < m ? l2.get(j) : INF; if (a <= b) { ans.add(a); i++; } else { ans.add(b); j++; } } return ans; } void dfs(TreeNode root, List<Integer> list) { if (root == null) return ; dfs(root.left, list); list.add(root.val); dfs(root.right, list); } } 复制代码
- 时间复杂度：令 nn 和 mm 分别为两棵树的节点数量，跑中序遍历的复杂度为 O(n + m)O(n+m)，构建答案复杂度为 O(\max(m, n))O(max(m,n))。整体复杂度为 O(n + m)O(n+m)
- 空间复杂度：O(n + m)O(n+m)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1310 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
