전에 비슷한 문제를 풀어본 것 같다. preorder는 root -> left -> right의 순서로 traverse하므로, preorder의 첫 번째 원소가 root이다.
inorder는 left -> root -> right의 순서로 traverse하므로, preorder에서 찾은 root 값을 inorder에서 찾으면 root값의 앞쪽 subarray는 left, 뒷쪽 subarray는 right subtree이므로 두 subtree에서 위의 작업을 반복한다. postorder는 left -> right -> root 순서이므로 left, right subtree 순서로 divide하고 그 다음에 root를 방문한다.
이때 함수 인자로 subtree의 inorder 배열에서의 start, end 인덱스와 현재 root가 preorder 배열에서 몇 번째 위치에 있는지를 넘겨주었다. start, end 인덱스는 inorder에서의 root 인덱스 앞뒤로 업데이트해주면 되므로 어렵지 않았는데, preorder 배열에서의 root 인덱스 위치를 갱신해주는게 약간 헷갈렸다.
preorder 배열에서 root는 무조건 첫 번째 원소이므로 left subtree의 inorder root index는 현재 root index + 1이다. 전체 inorder에서 left랑 root을 제외하면 right subtree이므로 (left subtree의 size) + now + 1가 right subtree의 inorder root index이다.
구현
#include <iostream>
#include <vector>
using namespace std;
vector<int> preorder;
vector<int> inorder;
void solve(int start, int end, int now, int n) { // inorder의 start idx, inorder의 end idx, preorder의 root idx, tree의 size
if (start > end) return;
int root, rootIdx, i;// inorder에서의 idx
root = preorder[now];
// rootIdx 구하기
for (i = start; i <= end; i++) {
if (inorder[i] == root) {
rootIdx = i;
// rootIdx를 기준으로 앞은 left, 뒤는 right
solve(start, rootIdx - 1, now + 1, n); // left subtree
// 분할된 preorder 배열에서 (sub)root는 언제나 첫 번째 원소이다.
// 그래서 right subtree의 root는 right subtree의 첫 번째 원소이고,
// 전체 inorder에서 left랑 root을 제외하면 right subtree이므로
// (left subtree의 size) + now + 1가 right subtree의 rootIdx이다.
solve(rootIdx + 1, end, now + (rootIdx - start) + 1, n); // right subtree.
cout << root << " "; // root
break;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int T, n, i, tmp;
cin >> T;
while (T--) {
cin >> n;
preorder.clear();
inorder.clear();
for (i = 0; i < n; i++) {
cin >> tmp;
preorder.push_back(tmp);
}
for (i = 0; i < n; i++) {
cin >> tmp;
inorder.push_back(tmp);
}
solve(0, n - 1, 0, n); // preorder의 맨 앞 노드는 root
cout << endl;
}
return 0;
}