【LeetCode 5296】All Elements in Two Binary Search Trees【Medium】【JAVA】

1. 题目

题目链接：https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

2. 题意

题目要求是合并两个搜索二叉树，合并成为一个List

3. 方法

3.1 思路

比较简单的做法，由于两棵树都是二叉搜索树，通过中序遍历，输出有序的数组，再将两个数组进行合并，时间复杂度上为O(n)。

3.2 代码

    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        inorderTraversal(root1, list1);

        List<Integer> list2 = new ArrayList<>();
        inorderTraversal(root2, list2);

        List<Integer> list = new ArrayList<>();
        int i1 = 0, i2 = 0;
        while (i1 < list1.size() && i2 < list2.size()) {
            if (list1.get(i1) > list2.get(i2)) {
                list.add(list2.get(i2++));
            } else {
                list.add(list1.get(i1++));
            }
        }

        while (i1 < list1.size()) {
            list.add(list1.get(i1++));
        }
        while (i2 < list2.size()) {
            list.add(list2.get(i2++));
        }

        return list;
    }

	// 中序遍历
    private void inorderTraversal(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left, list);
        list.add(root.val);
        inorderTraversal(root.right, list);
    }

3.3 运行结果

4. 相关链接

本题代码的github链接
LeetCode Top 100 Liked Questions 题目
其他LeetCode题目