[백준] 알고리즘 분류(트리,JAVA)4256번, 트리

문제 링크

4256번: 트리

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 전위 순회와 중위 순회를 한 결과가 주어집니다.

2. 입력된 정보를 가지고 후위 순회를 탐색하는 과정을 결과로 출력합니다.

3. 주어지는 트리는 이진 트리입니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 전위 순회와 중위 순회에 대한 정보를 이용하여 후위 순회 탐색을 진행합니다.

 

3. 후위 순회 탐색 결과를 출력합니다.

 

후위 순회

 

후위 순회는 기본적으로 Left → Right → Root 순으로 탐색을 진행합니다.

 

문제에서 나와있는 트리르 후위 순회 진행하면

Left Right Root

5 - 8 - 4- 6 - 2 - 1 - 7 - 3

중위 순회에 특징은

Left - Root - Right으로 표현되기 때문에

Root에 왼쪽에 있는 값들은 Left에 있는 자식 노드들

Root에 오른쪽에 있는 값들은 Right에 있는 자식 노드들

 

Root가 3이면

[5 - 6 - 8 - 4] - 3 - [1 - 2 - 7]으로 표현할 수 있습니다.

 

전위 순회에 특징은

Root - Left - Right으로 표현되기 때문에

첫 방문하는 노드는 Root 노드입니다.

3 - 6 - 5 - 4 - 8 - 7 - 1 - 2

 

Left를 먼저 탐색하기 때문에 RootIndex + 1은 Left에 Root노드가 됩니다.

Right는 Left를 먼저 탐색한 이후에 탐색되기 때문에 Left 자식노드 만큼 이동한 후 Right에 Root가 나옵니다.

 

중위 순회에서 Left 자식노드가 몇개 있는지 확인이 가능하다.

3 - 6 - 5 - 4 - 8 - 7 - 1 - 2

[5 - 6 - 8 - 4] - 3 - [1 - 2 - 7]

 

왼쪽 자식노드(4개) : 5 6 8 4

오른쪽 자식 노드(3개) : 1 2 7

 

Left의 Root노드는 : RootIndex[0] + 1 = 1 : 6

Right의 Root노드는 : RootIndex[0] + 4 + 1 : 7

위에 그림을 살펴보시면  Left와  Right를 따로 구분된 트리라고 보시면 Root인 것으로 확인할 수 있습니다.

 

요약.

 

전위 순회에 값으로 각 Root노드가 되는 값을 결정

중위 순회에서는 왼쪽 자식 노드와 오른쪽 자식 노드가 개수와 무엇이 있는지 확인

 

 

예제입력 1.

※테스트케이스 1번만 진행하는 과정을 보여드리겠습니다.

 

1. 입력된 정보를 저장합니다.

 

N : 4

Pre(전위) : 3 2 1 4
In(중위) : 2 3 4 1

 

 

2. 전위 순회와 중위 순회에 대한 정보를 이용하여 후위 순회 탐색을 진행합니다.

 

전위 탐색과 중위 탐색으로 아래와 같은 트리의 형태

후위 탐색을 진행하면

Left - Root - Right

2 - 4 - 1 - 3

 

3. 후위 순회 탐색 결과를 출력합니다.

 

2 4 1 3결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리 탐색의 정보를 띄어쓰기 기준 나누었습니다.
• postOrder함수를 통해 전위/중위 순회에 대한 값을 이용하여 후위 순회를 진행합니다.
• 각 테스트케이스의 후위 순회에 결과를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• postOrder함수는 후위 순회로써 Left - Right - Root순으로 탐색합니다.
• postOrder함수에서 전위 순회 값들을 이용해서 Root가 되는 노드를 구합니다.
• postOrder함수에서 중위 순회 값들을 이용해서 왼쪽/오른쪽 자식노드들을 나눕니다.

 

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    static StringBuilder sb = new StringBuilder();	//후위 순회 정보 저장 StringBuilder
    static int[] in, pre;	//전위, 중위 순회 입력값 저장 배열
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        //각 TC 진행
        for(int i=0;i<T;i++){
            int N = Integer.parseInt(br.readLine());
            in = new int[N+1];
            pre = new int[N+1];
            st = new StringTokenizer(br.readLine()," ");
            //전위 순회 저장
            for(int j=0;j<N;j++)
                pre[j] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine()," ");
            //중위 순회 저장
            for(int j=0;j<N;j++)
                in[j] = Integer.parseInt(st.nextToken());
            postOrder(0, 0, N);		//후위 순회 시작
            sb.append("\n");
        }
        bw.write(sb.toString() + "");	//각 후위 순회 정보 BufferedWriter저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //후위 순회 진행하는 함수
    static void postOrder(int root, int start, int end){
        int r = pre[root];		//Root 값
        //InOrder 범위 탐색
        for(int i=start;i<end;i++){
            if(r == in[i]){		//Root값 찾았을 때
                //Left는 RootIndex + 1
                postOrder(root+1, start, i);		//Left
                //Right는 RootIndex + Left자식 수(i - start) + 1
                postOrder(root+(i - start + 1), i + 1, end);	//Right
                sb.append(r).append(" ");		//Root
                return;
            }
        }
    }
}