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

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        int size1 = list1.size(), size2 = list2.size();
        List<Integer> ans = new ArrayList<>(list1.size() + list2.size());
        int p1 = 0, p2 = 0;
        while (p1 < size1 && p2 < size2) {
            int n1 = list1.get(p1);
            int n2 = list2.get(p2);
            if (n1 < n2) {
                ans.add(n1);
                p1++;
            } else {
                ans.add(n2);
                p2++;
            }
        }
        if (p2 != size2) {
            p1 = p2;
            size1 = size2;
            list1 = list2;
        }
        while (p1 < size1) ans.add(list1.get(p1++));
        return ans;
    }

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