(Leetcode 刷题) 两颗二叉搜索树的所有元素※

题目描述

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

解法1 中序遍历得到升序序列，再排序

我们知道了中序遍历的二叉搜索树的结果为非降序序列，将两个非降序序列排序，效率很低，毕竟最后都要排序，没必要追求非降序序列。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new LinkedList<>();
        List<Integer> list2 = new LinkedList<>();
        inorder(root1,list1);
        inorder(root2,list2);
        
        //排序
        List<Integer> list = new ArrayList<>();
        int a = 0;
        int b = 0;
        for(int i = 0; i < list1.size() + list2.size(); i++){
            if(a<list1.size() && b < list2.size()){
                int tmp1 = list1.get(a);
                int tmp2 = list2.get(b);
                if(tmp1 > tmp2){
                    list.add(tmp2);
                    b++;
                }else{
                    list.add(tmp1);
                    a++;
                }
            }
        }

        while( a < list1.size()){
            list.add(list1.get(a++));
        }

        while( b < list2.size()){
            list.add(list2.get(b++));
        }
        return list;
    }

    public void inorder(TreeNode root, List<Integer> list ){
        if(root == null){
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}

解法2 遍历两棵树，再排序

与上面的区别是遍历时不在乎顺序，到最后一步统一排序。

class Solution {
    //遍历两棵树，把结果放在res里
    List<Integer> res = new ArrayList<>();
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {  
         get(root1);
         get(root2);
         //直接调用封装好的排序
         Collections.sort(res);
         return res;
    }
    private void get(TreeNode root){
        if(root != null){
            res.add(root.val);
            get(root.left);
            get(root.right);
        }
    }
}

解法3 在树的遍历的过程中进行排序

先遍历得到一棵树的非降序排序(中序遍历)，遍历第二棵树的时候排序得到最终结果。

遍历第一棵树得到一个叫res1的队列，res1中是非降序的。
遍历第二棵树的第一个节点(中序遍历第一个节点是最小的节点)的时候，判断遍历到的节点值与res1的最小值的大小。如果res1中的元素小，将res1中比第二棵树最小节点还小的所有节点存入ans中(ans是一个存放最后结果的list)，随后再存第一个节点。重复以上过程，可以得到含有全部第二棵树节点和(可能)部分第一棵树节点的list ans。
如果res1还有剩下的值，把这些值加在ans的后面，返回最终结果。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        Queue<Integer> res1 = new LinkedList<>();
        List<Integer> ans = new LinkedList<>();
        helper(root1, res1);
        helper2(root2, res1, ans);
        //res1还有可能存在没有加入的节点，这些节点比第二棵树的最大结点还大
        while (!res1.isEmpty()) ans.add(res1.poll());
        return ans;
    }
    
    //中序遍历第一棵树
    private void helper(TreeNode node, Queue<Integer> res) {
        if (node == null) return;
        helper(node.left, res);
        res.offer(node.val);
        helper(node.right, res);
    }
    
    //中序遍历第二棵树
    private void helper2(TreeNode node, Queue<Integer> res, List<Integer> ans) {
        if (node == null) return;
        helper2(node.left, res, ans);
        
        //res1中比当前遍历节点小的先加入ans中
        while (!res.isEmpty() && node.val > res.peek()) {
            ans.add(res.poll());
        }
        ans.add(node.val);

        helper2(node.right, res, ans);
    }
}