[백준] 2263번 트리의 순회

트리의 순회(https://www.acmicpc.net/problem/2263)

---

1. 이해하기

• 인오더와 포스트오더로 나타내어진 트리를 프리오더로 나타내는 것이다.
• 인오더는 left root right, 포스트오더는 left right root 형태로 나타내어진다.
• 포스트오더에서 가장 오른쪽이 root이므로 이것을 이용해 인오더에서 left의 길이를 구한다. 구한 길이를 바탕으로 왼쪽과 오른쪽을 분할하여 다시 구한다.

• 

---

2. 구현하기

• solve(is,ie,ps,pe): 인오더의 시작,끝점과 포스트오더의 시작,끝점을 받는다.

  • 포스트오더에서 구한 root를 가지고 인오더에서 root의 위치(ir)를 찾는다. 그 이후에 루트의 왼쪽에 해당하는 길이(l)를 구하고 그 길이를 바탕으로 트리의 왼쪽과 오른쪽을 분할한다.
  • solve(is,ir-1,ps,ps+l-1) - 왼쪽
  • solve(ir+1,ie,ps+l,pe-1) - 오른쪽

  void solve(int is, int ie, int ps, int pe) {
      if(is > ie or ps > pe) return;
      int root = postorder[pe];
      cout << root << ' ';
      int ir = position[root];
  
      int left = ir-is;
      solve(is,ir-1,ps,ps+left-1);
      solve(ir+1,ie,ps+left,pe-1);
  }

• position은 inorder에서 숫자의 위치를 담고 있는 배열이다. root를 inorder에서 찾기위해 반복문을 이용해도 되지만 한번에 찾아내기 위하여 position배열을 이용한다.

---

3. 전체코드

#include <iostream>
using namespace std;

int inorder[100000], postorder[100000];
int position[100001];

void solve(int is, int ie, int ps, int pe) {
    if(is > ie or ps > pe) return;
    int root = postorder[pe];
    cout << root << ' ';
    int ir = position[root];

    int left = ir-is;
    solve(is,ir-1,ps,ps+left-1);
    solve(ir+1,ie,ps+left,pe-1);
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> inorder[i];
    for(int i = 0; i < n; i++) cin >> postorder[i];
    for(int i = 0; i < n; i++) {
        position[inorder[i]] = i;
    }
    solve(0,n-1,0,n-1);
    cout << '\n';
    return 0;
}