# 1305. All Elements in Two Binary Search Trees
###### tags: `Leetcode` `Medium` `FaceBook` `DFS`
Link: https://leetcode.com/problems/all-elements-in-two-binary-search-trees/
## 思路 $O(M+N)$ $O(M+N)$
### iterative one pass
和inorder traversal的iterative版差不多，拿到一个node，先找到最左边的（过程中把经历过的node放进stack），然后比较栈顶元素，某个元素pop出来之后先把值加进list，然后遍历当前node的right child
### recursive two pass
首先把两个tree inorder traversal，得到两个排好序的list/arr，然后再把他们merge起来就是答案
一开始的merge想法是用[0088. Merge Sorted Array](https://hackmd.io/uNTJQ2RaRAWsjYu7prqQlQ)，但其实这道题已经不追求O(1)了，因此可以再建一个array存结果，不需要用那道题的方法
但是实作的时候还是有一个点值得注意，因为写的时候是合并两个list，所以需要先指定答案list的长度，这样才能从后往前加，但是如果把line7写成

会发现ans的长度还是0，因此后面插入的时候就会有问题,因此**想要指定list长度，一定要用

后面用set放元素进去，而不是add**
## Code
### iterative one pass

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        while(root1!=null || root2!=null || !stack1.isEmpty() || !stack2.isEmpty()){
            while(root1!=null){
                stack1.push(root1);
                root1 = root1.left;
            }
            while(root2!=null){
                stack2.push(root2);
                root2 = root2.left;
            }
            if(stack2.isEmpty() || !stack1.isEmpty() &&stack1.peek().val<=stack2.peek().val){
                root1 = stack1.pop();
                ans.add(root1.val);
                root1 = root1.right;
            }
            else if(stack1.isEmpty() || stack2.peek().val<stack1.peek().val){
                root2 = stack2.pop();
                ans.add(root2.val);
                root2 = root2.right;
            }
        }
        return ans;
    }
}

### recursive two pass

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        inorder(root1, list1);
        List<Integer> list2 = new ArrayList<>();
        inorder(root2, list2);
        List<Integer> ans = Arrays.asList(new Integer[list1.size()+list2.size()]);
        int idx1 = list1.size()-1;
        int idx2 = list2.size()-1;
        int idx = list1.size()+list2.size()-1;
        while(idx1>=0 && idx2>=0){
            if(list1.get(idx1)>list2.get(idx2)){
                ans.set(idx, list1.get(idx1));
                idx1--;
            }
            else{
                ans.set(idx, list2.get(idx2));
                idx2--;
            }
            idx--;
        }
        while(idx2>=0){
            ans.set(idx, list2.get(idx2));
            idx2--;
            idx--;
        }
        while(idx1>=0){
            ans.set(idx, list1.get(idx1));
            idx1--;
            idx--;
        }
        return ans;
    }
    public void inorder(TreeNode root, List<Integer> arr){
        if(root==null) return;
        inorder(root.left, arr);
        arr.add(root.val);
        inorder(root.right, arr);
    }
}