[백준] 2263번 트리의 순회

2263 트리의 순회

문제

---

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

---

첫째 줄에 프리오더를 출력한다.

---

풀이)

순회방법을 미리 알았어야 풀기 쉬운 문제이다.

다음과 같은 트리가 있을 시

1. inorder : 중위순회

 - left→root→right순으로 읽는다.

 - 위의 그림을 읽는 순서 : 2→1→3

2. postorder : 후위순회

 - left→right→root 순으로 읽는다.

 - 위의 그림을 읽는 순서 : 2→3→1

3. preorder : 전위순회

 - root→left→right 순으로 읽는다.

 - 위의 그림을 읽는 순서 : 1→2→3

문제에서는 inorder와 postorder로 읽는 방법을 주는데,

inorder 는 left→root→right /// postorder 는 left→right→root순이다. 

구해야 할 것은 preorder이므로 root부터 출력해줘야 하는데 이를 주어진 order들을 이용하면 된다.

이용과정

① postorder의 맨 마지막 번호가 트리의 root이므로, 그 root 번호를 먼저 출력해준다.

② root번호를 기준으로 left subtree & right subtree로 나누어준다. 

    나눌 때는 inorder를 이용한다.

    inorder중 tree의 root 번호가 어느 위치에 있는지 알아내어 그 위치를 기준으로 왼쪽, 오른쪽 나누면 된다.

③ 각각의 subtree의 root를 출력하고, subtree의 root을 기준으로 다시 ②번 수행

주의할점

preorder는 root→left→right 순으로 출력해야하므로

subtree로 나누고 subtree의 root를 출력할 때 left subtree의 root를 먼저 출력해줘야한다.

코드)

//2263 트리의 순회
#include <stdio.h>
using namespace std;
int n;
int inorder[100002];//중위순회, left->root->right
int postorder[100002];//후위순회, left->right->root
int index[100002]; //트리노드 번호가 inorder에서 어느 위치에 있는지 저장
 
//출력할 preorder 전위순회 root->left->right
//is : inorder 구역의 처음 인덱스 ie: inorder 구역의 마지막 인덱스
//ps : postorder 구역의 처음 인덱스 pe: postorder 구역의 마지막 인덱스
void Preorder(int is, int ie, int ps, int pe) {
    if (is > ie || ps > pe) return;
    int root = postorder[pe]; //루트 노드의 번호
    printf("%d ", root);
    int pos = index[root]; //inorder에서 루트 정점이 어디에 위치해있는지
 
    //루트를 기준으로 left , right subtree로 나눔
    int left = pos - is;//왼쪽 subtree size
    Preorder(is, pos - 1, ps, ps + left - 1);//Preorder은 root다음에 왼쪽 출력해야하니깐 왼쪽함수 먼저 호출
    Preorder(pos + 1, ie, ps + left, pe - 1);
}
 
int main() {
    scanf("%d", &n);
    //인오더 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &inorder[i]);
        index[inorder[i]] = i;
    }
    //포스트오더 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &postorder[i]);
    }
    Preorder(1, n, 1, n);
    return 0;
}