题目大意：
两棵二叉搜索树中的所有元素
给你 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]之间。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1305
解题思路分析：
这道题分为2步，首先我们需要将每棵树的节点都按照升序顺序遍历出来。由于是二分查找树，符合当前节点左侧的子节点都小于当前节点，并且右侧所有子节点都大于当前节点的规律。因此我们可以从根节点开始按照中序遍历方式的顺序遍历所有节点，该方式遍历的顺序一定能够保证数字由小到大排列。
中序遍历：
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树
分别遍历完两颗树之后，我们可以得到2个升序排序好的数组，然后再使用Merge Sort将2个数组合并即可。Merge Sort的原理很简单，由于两个数组已经排序好，我们使用2个指针分别指向2个数组的首元素，比较2个指针指向的元素，将较小的一个放入新的数组，同时向右移动该下标，如果两个数相同，可以将其同时放入新的数组，并同时向右移动2个下标，重复以上步骤，直到某一个下标到达该数组末尾。然后再将下标没到末尾的数组的剩余部分加入到新数组即可。
实现代码：
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> list1 = new ArrayList<>(); // 第一棵树所有节点
List<Integer> list2 = new ArrayList<>(); // 第二棵树所有节点
getNodes(root1, list1); // 中序遍历第一棵树
getNodes(root2, list2); // 中序遍历第二棵树
// 返回结果
List<Integer> res = new ArrayList<>();
int i1=0,i2=0; // 定义2个指针
// 开始Merge Sort
while(i1<list1.size()&&i2<list2.size()){
if(list1.get(i1)<list2.get(i2)){
res.add(list1.get(i1++));
}else{
res.add(list2.get(i2++));
}
}
while(i1<list1.size()) res.add(list1.get(i1++));
while(i2<list2.size()) res.add(list2.get(i2++));
return res;
}
// 递归中序遍历方法
void getNodes(TreeNode root, List<Integer> list){
if(root==null) return;
if(root.left!=null) getNodes(root.left, list);
list.add(root.val);
if(root.right!=null) getNodes(root.right, list);
}本题解法执行时间为15ms。
Runtime: 15 ms, faster than 85.33% of Java online submissions for All Elements in Two Binary Search Trees.
Memory Usage: 42.2 MB, less than 100.00% of Java online submissions for All Elements in Two Binary Search Trees.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1305-all-elements-in-two-binary-search-trees-解题思路分析/