JAVA练习260-两棵二叉搜索树中的所有元素

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

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

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

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

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees

二叉搜索树中序遍历就为升序排列的结果，因此我们可以定义两个列表来获取两棵树的升序列表，然后定义双制针分别指向两个列表的首索引，进行比较添加较小的数，直到一个列表遍历完，再将另一个没有遍历完的列表添加到结果列表即可。

时间复杂度：O(m + n)         m、n 为两个二叉树的节点数
空间复杂度：O(m + n)

class Solution {

    public List getAllElements(TreeNode root1, TreeNode root2) {
        // 两个二叉树的升序排列列表和结果列表
        List list1 = new ArrayList<>(), list2 = new ArrayList<>(), res = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        // 定义双指针,两个列表长度
        int i = 0, j = 0, len1 = list1.size(), len2 = list2.size();
        // 遍历两个列表
        while(i < len1 && j < len2){
            int a = list1.get(i), b = list2.get(j);
            if(a <= b){
                res.add(a);
                i++;
            }
            else{
                res.add(b);
                j++;
            }
        }
        // 添加未添加完的值
        if(i == len1){
            while(j < len2){
                res.add(list2.get(j++));
            }
        }
        else{
            while(i < len1){
                res.add(list1.get(i++));
            }
        }
        return res;
    }

    // 中序遍历
    public void dfs(TreeNode root, List list){
        if(root == null){
            return;
        }
        dfs(root.left, list);
        list.add(root.val);
        dfs(root.right, list);
    }
}