# [Gold I] 트리의 순회 [문제 링크](https://www.acmicpc.net/problem/2263) ## 문제 설명 <p>n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.</p> ## 출력 <p>첫째 줄에 프리오더를 출력한다.</p> ## 풀이 #### postOrder의 마지막 값이 루트라는 특징과, inOrder의 노드 왼쪽에는 왼쪽 자식들이, 오른쪽에는 오른쪽 자식들이 배치된다는 특징을 이용해서 재귀로 풀 수 있다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 100'000; int inorderElementIdx[MAX+1]; int postorder[MAX]; /** * inorder : left - root - right * postorder : left - right - root * preorder : root - left - right */ void printPreorder(int postL, int postR, int inL, int inR) { int root = postorder[postR]; int leftCnt = inorderElementIdx[root]-inL; cout << root << ' '; if(postL<=postL+leftCnt-1) printPreorder(postL, postL+leftCnt-1, inL, inorderElementIdx[root]-1); if(postL+leftCnt<=postR-1) printPreorder(postL+leftCnt, postR-1, inorderElementIdx[root]+1, inR); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i<n;i++) { int inorder; cin >> inorder; inorderElementIdx[inorder]=i; } for(int i=0;i<n;i++) cin >> postorder[i]; printPreorder(0, n-1, 0, n-1); } ```