[BOJ] 2263 트리의 순회 C++

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

2263번: 트리의 순회

트리를 공부 중이라면 꼭 풀어야 할 문제라고 생각한다. 전위 순회, 중위 순회, 후위 순회의 관계를 알아야 풀 수 있는 문제이다.

위와 같은 트리를 중위 탐색 후위 탐색한 결과이다.

중위 탐색과 후위 탐색 관련성

위를 보고 재귀를 사용하면 쉽게 풀 수 있을 것이라 생각했다.

중위 순회은 루트노트 1의 기준으로 보았을 때, 1의 왼쪽에는 왼쪽 서브트리의 노드들이 오른쪽에는 오른쪽 서브트리의 노드들이 있음을 알 수 있었다.  

후위 순회는 처음에 직관적으로 중위 순회에서 구한 root_idx(루트노드의 인덱스)를 가지고 와서 후위 순회에

왼쪽 서브트리의 시작인덱스 = 후위 순회의 시작인덱스

왼쪽 서브트리의 끝인덱스 = root_idx-1

오른쪽 서브트리의 시작인덱스 = root_idx

오른쪽 서브트리의 끝인덱스 = 후위 순회의 끝 인덱스-1

이렇게 했는데 왼쪽서브트리는 잘 구했지만 오른쪽 서브트리를 구하는 과정에서 오류가 났다.

후위 순회이 어떻게 나누어지는지를 가지고 꽤 고민했는데 1시간 정도 고생하다가 결국 다른 분들의 코딩을 보게 되었다...

문제는 왼쪽 서브트리의 끝 인덱스와 오른쪽 서브트리의 시작 인덱스 값이 잘못돼서 였다. 

root_idx를 기준으로 나누는게 아니라 (후위 순회의 시작점-중위 순회의 시작점+root_idx)를 기준으로 나누어야 했다.

뭔가 직관적으로 와닿지는 않지만 이렇게 해줘야 root_idx가 후위 순회의 오른쪽 서브트리 시작점보다 커지는 것을 방지해 준다.

그냥 외워야겠다^^

중위 순회와 후위 순회가 주어졌을 때, 후위 순회는

후위 순회의 시작점-중위 순회의 시작점+root_idx

후위 순회의 시작점-중위 순회의 시작점+root_idx

후위 순회의 시작점-중위 순회의 시작점+root_idx

후위 순회의 시작점-중위 순회의 시작점+root_idx

로 나누어준다!

 

코드

#include <iostream>

using namespace std;

int N;

int inorder[100000];

int postorder[100000];

 

void find_preorder(int in_start,int in_end,int po_start, int po_end){

    //각각의 시작점이 끝점보다 커지면 리턴

    if(in_start>in_end||po_start>po_end) return;

    int root_idx=-1;

    for(int i=in_start;i<=in_end;i++){

        //후위 순회의 끝은 항상 루트노트라는 것을 활용해서 중위 순회의 루트노드 구하기

        if(inorder[i]==postorder[po_end]){

            root_idx=i;

            break;

        }

    }

    cout<<inorder[root_idx]<<" ";

    //왼쪽 서브트리 먼저 po_start-instart+root_idx로 나눈다.

    find_preorder(in_start,root_idx-1,po_start,po_start+root_idx-in_start-1);

    //오른쪽 서브트리

    find_preorder(root_idx+1,in_end,po_start+root_idx-in_start,po_end-1);

}

 

int main(){

    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);

    cin>>N;

    for(int i=0;i<N;i++) cin>>inorder[i];

    for(int i=0;i<N;i++) cin>>postorder[i];

    find_preorder(0,N-1,0,N-1);

    return 0;

}