[Leet] - 1305. All Elements in Two Binary Search Trees

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

void dfs(TreeNode* root, vector<int>& v)
    {
        if(root->left) dfs(root->left,v);
        v.push_back(root->val);
        if(root->right) dfs(root->right,v);
    }

DFS 실행 결과 1,3,4,5,6,7,8 순으로 저장

C++풀이

class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> v1,v2;
        vector<int> ans;
        int s1=0;
        int s2=0;
        
        if(root1) dfs(root1,v1);
        if(root2) dfs(root2,v2);
        sort(v1.begin(),v1.end());
        sort(v2.begin(),v2.end());
        
        while(s1<v1.size() && s2<v2.size())
        {
            if(v1[s1]<=v2[s2]) {ans.push_back(v1[s1]);s1++;}
            else {ans.push_back(v2[s2]);s2++;}
        }
        while(s1<v1.size()) ans.push_back(v1[s1++]);
        while(s2<v2.size()) ans.push_back(v2[s2++]);

        return ans;
    }
    
    void dfs(TreeNode* root, vector<int>& v)
    {
        if(root->left) dfs(root->left,v);
        v.push_back(root->val);
        if(root->right) dfs(root->right,v);
    }
};

시간 개선 => merge사용