X

LEETCODE 1305. All Elements in Two Binary Search Trees 解题思路分析

题目大意:

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

给你 root1root2 这两棵二叉搜索树。

请你返回一个列表,其中包含 两棵树 中的所有整数并按 升序 排序。

示例 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-解题思路分析/
Categories: leetcode
kwantong: