[백준 4256] 트리

 

예제로 트리 구조를 유추해보자.

 

전위 순회 : 3 6 5 4 8 7 1 2

중위 순회 : 5 6 8 4 3 1 2 7

 

전위 순회는 루트부터 시작하고, 중위 순회는 루트를 중심으로 왼쪽 서브트리, 오른쪽 서브트리로 나뉜다.

전위 순회의 첫번째가 3이므로 루트 노드는 3이고 5 6 8 4 는 왼쪽 서브트리, 1 2 7 은 오른쪽 서브트리이다.

양 서브트리의 루트(최상단) 노드는 전위 순회의 첫번째 노드 이므로 각각 6, 7 이다.

루트 노트를 찾았으면 또 이등분하여 서브트리를 구한다.

 

시작 위치, 끝 위치, 루트 노드의 위치를 받아 재귀하여 구현하였다.

 

 

public class Main {
    
    static int pre[];
    static int in[];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        while(t-->0) {
            int n = sc.nextInt();
            pre = new int[n+1];
            in = new int[n+1];
            for(int i=0; i<n; i++)
                pre[i] = sc.nextInt();
            for(int i=0; i<n; i++)
                in[i] = sc.nextInt();
            
            postorder(0, n, 0);
            System.out.println();
        }
    }
    
    public static void postorder(int s, int e, int r) {
        for(int i=s; i<e; i++) {
            if(in[i] == pre[r]) {
                postorder(s, i, r+1);
                postorder(i+1, e, r+i-s+1);
                System.out.print(pre[r] + " ");
            }
        }
    }
}