(5639) 이진 검색 트리

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

단계별로 풀어보기

33단계(트리) 6번째

 

 

 

전위 검색에서 첫 번째 결과는 트리의 루트이다. 전위 검색은 이 루트의 값보다 작은 왼쪽 서브트리를 전부 탐색하고, 이 루트의 값보다 큰 오른쪽 서브트리를 전부 탐색한다.

따라서 이분 탐색으로 루트의 값보다 커지는 지점을 찾으면, 왼쪽 서브트리와 오른쪽 서브트리의 구간을 찾을 수 있다.

재귀를 이용해 각각의 서브트리에 대해 같은 방식을 적용하면 트리의 형태를 알 수 있고, 탐색이 끝난 뒤 루트 노드를 출력하면 후위 순회의 결과가 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  vector<int> inorder;

  int n;
  
  while(cin >> n)  inorder.push_back(n);
  
  auto func= [&](auto self, int s, int e) -> void {
    if(s>e)  return;
    
    int idx= upper_bound(inorder.begin()+s+1, inorder.begin()+e+1, inorder[s])-inorder.begin();
    
    self(self, s+1, idx-1);
    self(self, idx, e);
    cout << inorder[s] << "\n";
  };
  
  func(func, 0, inorder.size()-1);
  
  return 0;
}