[LeetCode] 1305. All Elements in Two Binary Search Trees

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

All Elements in Two Binary Search Trees - LeetCode

All Elements in Two Binary Search Trees - Medium

이진탐색트리가 두개 주어진다.

두 이진탐색트리의 모든 성분을 오름차순으로 정렬하는 문제다.

 

먼저, 벡터를 두개 만들어 각각의 이진탐색트리의 성분을 오름차순으로 저장한다.

오름차순으로 저장하는 방법은, 

먼저 왼쪽노드의 값을 저장하고, 해당 노드의 값을 저장하고, 오른쪽 노드의 값을 저장하는 과정을 재귀반복해주면 된다.

그 후에는 각각의 벡터를 한칸씩 이동시키며 서로 비교하여 작은값을 넣어주면 된다.

 

전체 풀이 코드

class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> vec1,vec2,ret;
        int i=0,j=0;
        run(root1, &vec1);
        run(root2, &vec2);
        while (i<vec1.size() || j<vec2.size()) {
            if (i<vec1.size() && j<vec2.size()) {
                if (vec1[i] < vec2[j]) ret.push_back(vec1[i++]);
                else ret.push_back(vec2[j++]);
            } else if (i<vec1.size()) ret.push_back(vec1[i++]);
            else ret.push_back(vec2[j++]);
        }
        return ret;
    }
    void run(TreeNode* node, vector<int>* vec) {
        if (!node) return;
        run(node->left, vec);
        (*vec).push_back(node->val);
        run(node->right, vec);
    }
};