(2263) 트리의 순회

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

단계별로 풀어보기

33단계(트리) 5번째

 

 

 

중위 순회와 후위 순회로 전위 순회 결과를 알아야 하는 문제.

후위 순회에서 마지막 결과가 현재 트리의 루트 노드이다. 이 노드를 중위 순회에서 찾으면, 노드를 기준으로 중위 순회의 왼쪽이 왼쪽 서브트리, 오른쪽이 오른쪽 서브트리이다. 각각의 서브트리를 다시 후위 순회에서 찾으면 마지막 결과가 서브트리의 루트 노드이다. 이를 재귀로 반복하면 된다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  
  cin >> n;
  
  vector<int> inorder(n+1), postorder(n+1), inorderindex(n+1);
  
  for(int i=1;i<=n;i++)  cin >> inorder[i];
  for(int i=1;i<=n;i++)  cin >> postorder[i];
  for(int i=1;i<=n;i++)  inorderindex[inorder[i]]= i;
  
  auto func= [&](auto self, int in_s, int in_e, int post_s, int post_e) -> void {
    if(in_s>in_e || post_s>post_e)  return;
    
    int root= inorderindex[postorder[post_e]];
    int sz= root-in_s;
    
    cout << inorder[root] << " ";
    
    self(self, in_s, root-1, post_s, post_s+sz-1);
    self(self, root+1, in_e, post_s+sz, post_e-1);
  };
  
  func(func, 1, n, 1, n);
  
  return 0;
}