[BOJ] 2263: 트리의 순회

[BOJ] 2263: 트리의 순회

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

이진 트리의 inorder와 postorder가 주어졌을 때, preorder를 구하는 문제이다.

각각을 간단히 정리해보자면 아래와 같다.

1. preorder (전위 순회)

: root -> 왼쪽 subtree -> 오른쪽 subtree 순으로 방문

=> 그래프에서의 dfs와 순서 동일

2. inorder (중위 순회)

: 왼쪽 subtree -> root -> 오른쪽 subtree 순으로 방문

3. postorder (후위 순회)

: 왼쪽 subtree -> 오른쪽 subtree -> root 순으로 방문

root를 언제 방문하냐에 따라 이름 붙여져있다.

inorder에서 중간 순서에 있는 node가 root가 되고, 그 node 기준 왼쪽이 left subtree, 오른쪽이 right subtree인 구조가 반복되어 root -> left -> right 순으로 재배치하면 된다.

라고 생각했는데, 마음대로 완전이진트리로 가정한 나의 실수였다...

후위 순회의 마지막 값은 항상 root 이기 때문에, 해당 노드를 기준으로 중위순회에서 left, right를 찾아내서 후위 순회 값들도 left, right로 분할하는 과정을 재귀적으로 반복하며 root를 출력하면 된다.

#include using namespace std; int in[100001]; int post[100001]; int idx[100001]; void dfs(int inStart, int inEnd, int postStart, int postEnd) { if (inStart > inEnd || postStart > postEnd) return; int root = idx[post[postEnd]]; int nLeft = root - inStart; int nRight = inEnd - root; printf("%d ", in[root]); dfs(inStart, root - 1, postStart, postStart + nLeft - 1); dfs(root + 1, inEnd, postStart + nLeft, postEnd - 1); } int main() { int n; scanf_s("%d", &n;); for (int i = 1; i <= n; i++) { scanf_s("%d", ∈[i]); idx[in[i]] = i; } for (int i = 1; i <= n; i++) { scanf_s("%d", &post;[i]); } dfs(1, n, 1, n); }

from http://gokong.tistory.com/12 by ccl(A) rewrite - 2021-10-01 17:26:20