BOJ 4256 - 트리

📌 문제 출처: BOJ 4256 - 트리

---

제목

(7/29 - Tree: BOJ 4256)

---

문제 유형

• 트리
• 전위/중위/후위 순회
• 재귀
• 분할정복

---

문제 요약

• 어떤 이진 트리의 전위(preorder) 순회와 중위(inorder) 순회가 주어진다.
• 이를 바탕으로 후위(postorder) 순회 결과를 구하라.

---

풀이 방법 도출

1. 전위 순회의 첫 값은 항상 루트 노드다.
2. 이 루트 값을 중위 순회에서 찾아 위치를 기준으로 왼쪽/오른쪽 서브트리로 나눈다.
3. 왼쪽, 오른쪽 서브트리를 재귀적으로 탐색하며 후위 순회를 구성한다.
4. 이 방식으로 후위 순회의 순서를 출력한다.

---

시간 복잡도

• 각 노드는 정확히 한 번씩 처리됨 → O(N)
• unordered_map을 사용하여 중위 배열에서 루트 인덱스를 O(1)에 찾음

---

C++ 코드

#include <bits/stdc++.h>
using namespace std;

void postOrder(int preStart, int inStart, int len,
               vector<int>& pre, vector<int>& in,
               unordered_map<int, int>& inIndex) {
  if (len == 0) return;

  int root = pre[preStart];
  int rootIdx = inIndex[root];
  int leftLen = rootIdx - inStart;
  int rightLen = len - 1 - leftLen;

  postOrder(preStart + 1, inStart, leftLen, pre, in, inIndex);                     // 왼쪽
  postOrder(preStart + 1 + leftLen, rootIdx + 1, rightLen, pre, in, inIndex);     // 오른쪽
  cout << root << ' ';                                                            // 루트 출력
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin >> t;

  while (t--) {
    int n;
    cin >> n;

    vector<int> pre(n), in(n);
    for (int i = 0; i < n; i++) cin >> pre[i];
    for (int i = 0; i < n; i++) cin >> in[i];

    unordered_map<int, int> inIndex;
    for (int i = 0; i < n; i++) {
      inIndex[in[i]] = i;
    }

    postOrder(0, 0, n, pre, in, inIndex);
    cout << '\n';
  }
}