[백준 4256번] 트리 (JAVA)

 

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

4256번: 트리

 

이 문제는 골드 2 문제로 전위 순회, 중위 순회 값이 주어졌을 때 이 두 개의 값을 토대로 후위 순회를 만드는 문제입니다.

---

전위 순회? 중위 순회? 후위 순회?

문제를 풀기에 앞서 전위 순회, 중위 순회, 후위 순회에 대해 설명하자면,

 

 

전위 순회(Preorder),중위 순회(Inorder), 후위 순회(Postorder)

먼저 전위순회는 루트 노드 -  왼쪽 노드 - 오른쪽 노드 순으로 탐색합니다. 따라서, 위 그림의 트리를 전위 순회로 탐색하면, [1,2,4,5,3,6,7]의 순서로 탐색하게 됩니다.

중위 순회는 왼쪽 노드 - 루트노드 - 오른쪽 노드 순으로 탐색합니다. 따라서 위 트리를 [4,2,5,1,6,3,7] 순으로 탐색합니다.

후위 순회는 왼쪽 노드- 루트 노드 - 오른쪽 노드 순으로 탐색합니다. 따라서 위 트리를 [4,5,2,6,7,3,1] 순으로 탐색합니다.

이 문제를 풀기 위해선 이 순회들의 개념에 대해서 알아야 합니다.

---

풀이

예시를 보면, 첫 번째 입력받는 값은 테스트 케이스의 수 T입니다. 그리고 두 번째로 입력받는 값은 해당 테스트케이스의 노드의 개수 N입니다. 세 번째는 전위 순회 결과 값인 PreOrder, 마지막 네 번째는 중위 순회 결과 값인 InOrder입니다. 

이 중 우리는 PreOrder 값과 InOrder 값을 이용해 이 문제를 풀 것입니다.

 

전위 순회(PreOrder)	3	2	1	4
중위 순회(InOrder)	2	3	4	1

 

아까 말했던 전위 순회의 순서를 기억하나요? 전위 순회의 순서는 루트 노드-왼쪽 노드-오른쪽 노드죠.

그렇다면 전위 순회의 첫 번째 인덱스에 위치한 노드인 3은, 이 트리의 루트 노드입니다. 

 

전위 순회(PreOrder)	3(루트)	2	1	4
중위 순회(InOrder)	2	3(루트)	4	1

 

자 그다음 중위 순회를 볼까요? 중위 순회의 순서는 왼쪽 노드 - 루트 - 오른쪽 루트입니다. 그 말은, 중위 순회 결과 값에서, 루트 노드 왼쪽에 있는 것은 왼쪽 노드, 루트 노드 오른쪽에 있는 것은 오른쪽 노드인 것이죠 

 

전위 순회(PreOrder)	3(루트)	2(왼쪽)	1(오른쪽)	4(오른쪽)
중위 순회(InOrder)	2(왼쪽)	3 (루트)	4(오른쪽)	1(오른쪽)

 

후위 순회의 순서는 왼쪽 노드- 오른쪽 노드- 루트 노드입니다. 따라서 저희는 루트의 왼쪽, 왼쪽 노드부터 탐색을 할 겁니다. 그렇기에 자신의 값을 제외하고 왼쪽, 오른쪽 값이 없을 때까지 재귀를 호출한 다음, 루트 값을 후위 순회 결과 값에 추가하면, 후위 순회 값을 완성하게 됩니다. 

 

예를 들어, 위의 표처럼 루트 왼쪽에 있는 노드들(2)을 이용해 재귀를 호출합니다. 그렇게 되면, 노드 2는 자기 노드를 제외하고 왼쪽, 오른쪽 노드가 없기 때문에, 자신의 노드를 후위 순회에 추가합니다. 그다음 전 단계로 돌아와서 이제 오른쪽 노드(4,1)를 탐색할 것입니다. 그렇게 되면

 

전위 순회(PreOrder)	1	4
중위 순회(InOrder)	4	1

 

이 표가 나오게 됩니다. 전 단계처럼 똑같이 찾아본다면

 

전위 순회(PreOrder)	1(루트)	4(왼쪽)
중위 순회(InOrder)	4(왼쪽)	1(루트)

 

이 값이 나오게 되므로, 후위 순회의 순서에 따라 왼쪽노드인 4부터 탐색하게 되고, 노드 4인 경우는 왼쪽, 오른쪽 노드가 없기 때문에 루트 노드인 자기 자신을 후위 순회 결과값에 추가합니다. 그리고  전 단계로 돌아와 탐색이 다 끝났으므로, 루트 노드인 1도, 후위 순회 결과 값에 추가합니다.

 

전위 순회(PreOrder)	3(루트)	2(왼쪽)	1(오른쪽)	4(오른쪽)
중위 순회(InOrder)	2(왼쪽)	3 (루트)	4(오른쪽)	1(오른쪽)

 

다시 전 단계로 돌아와서, 왼쪽 노드- 오른쪽 노드까지 탐색이 모두 완료 됐으므로 마지막 루트 노드인 3을 후위 순회 값에 추가해 줍니다. 따라서 후위 순회 결괏값은 [2,4,1,3]입니다. 

---

코드

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

public class Tree {
    static LinkedList<Integer> postList = new LinkedList<Integer>();

    public static void main(String args[]) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        try {
        	//테스트 케이스 입력
            int t = Integer.parseInt(br.readLine());
			//테스트케이스 횟수 만큼 반복
            for (int i = 0; i < t; i++) {
            	//입력
                int n = Integer.parseInt(br.readLine());
                String firstPre = br.readLine();
                String firstIn = br.readLine();
                String[] preTemp = firstPre.split(" ");
                String[] inTemp = firstIn.split(" ");
                LinkedList<Integer> preList = new LinkedList<Integer>();
                LinkedList<Integer> inList = new LinkedList<Integer>();
                for (int j = 0; j < n; j++) {
                    preList.add(Integer.parseInt(preTemp[j]));
                    inList.add(Integer.parseInt(inTemp[j]));
                }
                
                //preList,inList,전위순회 시작위치,전위 순회 끝나는위치,중위 순회 시작위치,중위 순회 끝나는위치
                GetTree(preList, inList, 0, n - 1, 0, n - 1);
                for (int j = 0; j < postList.size(); j++) {
                    System.out.print(postList.get(j) + " ");
                }
                System.out.println();
				//해당 테스트 케이스가 종료되면 후위 순회 변수는 전역으로 선언되어있으므로, 값 초기화
                postList.clear();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void GetTree(LinkedList<Integer> preorder, LinkedList<Integer> inOrder,
                               int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart <= preEnd) {//시작과 끝이 일치하면 공간이 없으므로 함수 종료
        	int root = inOrder.indexOf(preorder.get(preStart));//루트의 위치
            int leftSubtreeSize = root - inStart; //왼쪽 서브트리 사이즈는 루트의 위치에서 inStart의위치 빼기
            //왼쪽으로 탐색하는 재귀 메소드
            GetTree(preorder, inOrder, preStart + 1, preStart + leftSubtreeSize, inStart, root - 1);4
            //오른쪽으로 탐색하는 재귀메소드
            GetTree(preorder, inOrder, preStart + leftSubtreeSize + 1, preEnd, root + 1, inEnd);
			//탐색이 끝나면 자기 자신의 값 추가
            postList.add(preorder.get(preStart));
        }
    }
}

초기에 문제를 풀 때는 재귀를 호출할 때마다 부분 LinkedList를 만들어서 새로운 값들을 할당해 주는 방식으로 했지만, 그렇게 되면 쓸데없는 공간이 많이 생기게 되어 오류가 나더라고요. 그래서 초기에 할당해 준 LinkedList들을 이용해, 범위를 매 재귀마다 다르게 해, 효율적으로 공간을 사용하게 끔 코딩했습니다.

 

 

이 코드가 정답은 아닙니다. 그저 백준에서 맞았습니다! 표시가 뜬 코드일 뿐 더 최적화되고 좋은 코드들을 작성하신 분들도 계십니다. 이렇게 코딩을 한 사람이 있구나 하고 봐주시면 감사드리겠습니다