📝 문제 정보#
🧐 관찰 및 접근#
- 이진 검색 트리의 전위 순회 결과를 이용해서 후위 순회 결과를 찾아내자!
- 트리가 만들어져 있다면, 후위 순회를 하는건 쉬울텐데…
- 전위 순회는 (루트 - 왼쪽서브트리 - 오른쪽서브트리)를 방문한다.
- 왼쪽 서브트리의 값은 언제나 루트보다 작고, 오른쪽 서브트리의 값은 언제나 루트보다 크므로
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);
}
};