[LeetCode] 1008. Construct Binary Search Tree from Preorder Traversal

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

Construct Binary Search Tree from Preorder Traversal - LeetCode

Construct Binary Search Tree from Preorder Traversal

 

 

preordered 된 vector가 있다.

이 벡터는 그림의 트리를 왼쪽에 있는 자식노드를 우선으로 dfs로 나타낸 벡터다.

즉 가장 위의 8-> 왼쪽자식인 5-> 왼쪽자식인 1-> 5의 오른쪽자식인 7->8의 오른쪽자식인 10->12

이렇게 preordered 되어있다.

이를 일반적인 이진탐색트리를 나타내는 BFS 식으로 바꾸는 문제다.

 

문제를 보면 조금까다로워 보였지만 문제 조건에서 벡터의 길이가 100이하로 매우 간단했다.

그 말은 그냥 루트부터 계속해서 훑으며 이진 탐색 트리를 만들어도 된다는 말이다.

벡터의 성분마다 만들어진 루트노드부터 비교하여 작으면 왼쪽, 크면 오른쪽으로 배치해주면 된다.

 

아래는 그 방법으로 풀이한 코드다.

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root = new TreeNode(preorder[0]);
        for (int i=1; i<preorder.size(); i++) {
            TreeNode* cur = root;
            int val = preorder[i];
            while ((cur->left!=NULL && val<cur->val) || (cur->right!=NULL && val>cur->val)) cur = val<cur->val?cur->left:cur->right;
            if (val<cur->val) cur->left = new TreeNode(val);
            else cur->right = new TreeNode(val);
        }
        return root;
    }
};

 

제출은 정상적으로 되었지만 정석적인 풀이는 아닐터.

조금 생각해보다가 생각이 잘 되지 않아 풀이를 보았다.

 

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/discuss/1519094/C%2B%2B-Simple-and-Clean-Recursive-Solution-Explained

위는 보게된 풀이다. 

이를 다시 천천히 이해하며 조금 바꿔 옮겨적었다.

(혹시나 문제가 된다면 나중에 삭제하겠다.)

 

class Solution {
public:
    vector<int> vec;
    int idx;
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        this->vec = preorder;
        this->idx = 0;
        return run(INT_MAX);
        
    }
    TreeNode* run(int M) {
        if (idx==this->vec.size() || this->vec[idx]>M) return NULL;
        TreeNode* root = new TreeNode(this->vec[idx++]);
        root->left = run(root->val);
        root->right = run(M);
        return root;
    }
};

 

preorder된 순서를 이용한 풀이로,

왼쪽이 우선으로 되어있으니 왼쪽 노드부터 달아준다.

이때 바로 위 노드값보다 크면 NULL을 리턴해 끝내주고,

오른쪽 노드를 달러간다.

오른쪽 노드는 바로 위 노드가 아닌 그 위 노드와 비교하여

작으면 달아주고 크면 다시 NULL을 리턴하며, 그 다음 위 노드와 비교해서 달게 되는 풀이다.

 

이런생각을 잘 못하다니 반성하게 된다.