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

解法一

先分别进行先序遍历，得到升序数组，再将两数组归并。

/**
 * 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<>();
        preOrder(root1, list1);
        preOrder(root2, list2);
        return merge(list1, list2);
    }
    /**
     * 先序遍历
     *
     * @param root 当前根结点
     * @param list 结点值升序数组
     */
    private void preOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        preOrder(root.left, list);
        list.add(root.val);
        preOrder(root.right, list);
    }
    /**
     * 归并排序, 输入数组均已升序排列
     *
     * @param list1 数组1
     * @param list2 数组2
     * @return 升序排列的归并后数组
     */
    private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        ListIterator<Integer> iter1 = list1.listIterator();
        ListIterator<Integer> iter2 = list2.listIterator();
        List<Integer> ans = new ArrayList<>(list1.size() + list2.size());
        int e1, e2;
        while (iter1.hasNext() && iter2.hasNext()) {
            e1 = iter1.next();
            e2 = iter2.next();
            if (e1 < e2) {
                ans.add(e1);
                iter2.previous();
            } else {
                ans.add(e2);
                iter1.previous();
            }
        }
        while (iter1.hasNext()) {
            ans.add(iter1.next());
        }
        while (iter2.hasNext()) {
            ans.add(iter2.next());
        }
        return ans;
    }
}