BOJ 5639 이진 검색 트리

📝 문제 정보

링크: https://www.acmicpc.net/problem/5639

🧐 관찰 및 접근

이진 검색 트리의 전위 순회 결과를 이용해서 후위 순회 결과를 찾아내자!
- 트리가 만들어져 있다면, 후위 순회를 하는건 쉬울텐데…
- 전위 순회는 (루트 - 왼쪽서브트리 - 오른쪽서브트리)를 방문한다.
  - 왼쪽 서브트리의 값은 언제나 루트보다 작고, 오른쪽 서브트리의 값은 언제나 루트보다 크므로
  - ```
  50 (루트)
  ---
  30 (왼쪽 서브트리)
  24
  5
  28
  45
  ---
  98 (오른쪽 서브트리)
  52
  60
```
- 첫 입력에 대해, 이렇게 생각할 수 있지 않을까?
- 그리고 각 서브트리 또한 이진 검색트리이므로, 이를 재귀적으로 수행할 수 있다.
- 예를 들어, 왼쪽 서브트리에 대해서
- ```
30 (루트)
---
24 (왼쪽 서브트리)
5
28
---
45 (오른쪽 서브트리)
```
  - 위와 같이 말이다!
- 그렇다면, 재귀를 이용해서 트리를 구축하고 후위순회만 하면 끝난다.

💻 풀이

코드 (C++):

vector<int> v;

struct Node{
    int val = -1;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int s, int e){
        val = v[s];
        if(s == e) return;

        int idx = e+1;
        rep(i, s+1, e+1){
            if(v[i] > val){
                idx = i;
                break;
            }
        }
        
        if(s+1 <= idx-1) left = new Node(s+1, idx-1);
        if(idx <= e) right = new Node(idx, e);
    }
};

void postorder(Node* node){
    if(node == nullptr) return;
    postorder(node->left);
    postorder(node->right);
    cout << node->val << '\n';
}

void solve(){
    int x;
    while(cin >> x) v.push_back(x);
    Node* root = new Node(0, v.size()-1);
    postorder(root);
}

루트와의 값 비교에서 단조성이 있으므로, 이분탐색도 섞을 수 있다.
- 정렬되어있지 않아도 단조성만 있다면 이분탐색이 가능하다!!

struct Node{
    int val = -1;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int s, int e){
        val = v[s];
        if(s == e) return;

        int ok = e+1, ng = s;
        while(ok - ng > 1){
            int mid = (ok + ng) >> 1;
            if(v[mid] > val) ok = mid;
            else ng = mid;
        }
        int idx = ok;
        
        if(s+1 <= idx-1) left = new Node(s+1, idx-1);
        if(idx <= e) right = new Node(idx, e);
    }
};