백준 2263번 - 트리의 순회 / Java

문제

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

2263번: 트리의 순회

문제 접근방법이 꽤 어려웠던문제.

포스트오더와 인오더의 특징을 잘 활용해야지 풀 수 있었다.

포스트오더의 특성상 맨 마지막에 오는것이 루트이다.  인오더는 루트를 기준으로 왼쪽 오른쪽이 나뉜다.

따라서 포스트오더로 루트를 찾고 인오더로 왼쪽 오른쪽 노드를 찾아서 계속 작은 트리로 노드를 쪼개서 프리오더를

해주면 된다.

 

알고리즘

1. 포스트오더의 끝을 루트로 정하고 프리오더로 답을 출력해야하므로 일단 출력한다.

2. 루트를 기준으로 인오더의 왼쪽 오른쪽을 나눠서 재귀 탐색한다.

소스코드

/*
 * BOJ2263
 * 2020.02.03
 * Hyeonseong 
 */
import java.util.*;    
public class BOJ2263 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    int n;
    int inOrder[],postOrder[],position[];
    public Solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        inOrder = new int[n+1];
        postOrder = new int[n+1];
        position = new int[n+1];
        for(int i=0;i<n;i++) {
            inOrder[i] = scan.nextInt();
        }
        for(int i=0;i<n;i++) {
            postOrder[i] = scan.nextInt();
        }
        for(int i=0;i<n;i++) {
            position[inOrder[i]] = i; // 인오더에서 루트의 위치를 저장해주는 인덱스배열
        }
        solve(0,n-1,0,n-1);
    }
    public void solve(int inStart, int inEnd, int postStart, int postEnd) {
        if(inStart > inEnd || postStart > postEnd) return;
        int root = postOrder[postEnd]; // 포스트오더의 끝부분이 루트이다
        System.out.print(root+" ");
        int p = position[root];
        solve(inStart, p-1, postStart, postStart+(p-inStart)-1); // 왼쪽탐색
        solve(p+1,inEnd,postStart+(p-inStart),postEnd-1); // 오른쪽탐색
    }
}