[알고리즘] 백준 - 트리

백준 - 트리

다른 사람 풀이

import java.io.IOException;
import java.util.Scanner;

public class baekjoon_4256 {

    static int pre[];
    static int in[];

    public static void main(String[] args) throws IOException {
        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 start, int end, int root) {
        for(int i= start; i< end; i++) {
            if(in[i] == pre[root]) {
                postorder(start, i, root+1);
                postorder(i+1, end, root+i- start +1);
                System.out.print(pre[root] + " ");
            }
        }
    }
}

1. 전위 순회는 root -> left -> right, 중위 순회는 left -> root -> right, 후위 순회는 left -> rigt -> root 순으로 이루어진다.
2. 여기서 우리는 전위 순회로 루트를 구하고, 구한 루트를 기반으로 중위 순회를 통해 왼쪽, 오른쪽으로 탐색을 진행해나가고 부모를 출력해준다(후위 순회)

https://ghdic.github.io/ps/boj-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 이다.

https://baelanche.tistory.com/142

https://chobicalling.tistory.com/158