[백준] 단계별로 풀어보기(단계:29, 트리,JAVA)2263번, 트리의 순회

문제 링크

2263번: 트리의 순회

---

주의사항

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

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

---

문제 설명

---

접근 방법

트리

서로 다른 두 노드를 잇는 길이 하나뿐인 그래프

트리 구조 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 어떤 트리에 대하여 중위, 후위 순회한 결과를 통해 전위 순회한 결과를 출력해야 한다.

2. 노드의 정점은 1..n까지 중복이 없이 주어진다.

 

전위 순회

(루트)(왼쪽 자식)(오른쪽 자식)

 

중위 순회

(왼쪽 자식)(루트)(오른쪽 자식)

 

후위 순회

(왼쪽 자식)(오른쪽 자식)(루트)

 

후위 순회에서 얻을 수 있는 것은 마지막 값이 해당 트리의 루트 노드입니다.

 

중위 순회에서 얻을 수 있는 것은 후위 순회에서 얻은 루트 노드로 왼쪽 자식 노드와 오른쪽 자식 노드를 나눌 수 있습니다.

 

예를 들어 아래와 같은 트리일 때

 

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

후위 순회 : 2 7 4 5 3 6 1

 

후위 순회의 마지막 값 : 1  = 루트 노드

 

중위 순회에서 루트 노드(1) 기준 나누기

 

왼쪽 자식 노드 : 2 4 7

오른쪽 자식 노드 : 6 3 5

 

후위 순회에서는 (루트)를 마지막에 탐색하기 때문에 중위 순회에서 자식 노드에 개수만큼 왼쪽과 오른쪽으로 나뉜다.

왼쪽 자식노드 개수 3개, 오른쪽 자식노드 개수 3개

 

왼쪽 자식 노드 : 2 7 4

오른쪽 자식 노드 : 5 3 6

 

왼쪽 자식 노드의 루트 노드는

후위 순회의 마지막값 : 4 = 루트노드

 

위 과정을 반복하여 루트 노드들의 값들을 출력하면 전위 순회의 값을 얻을 수 있습니다.

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

 

문제에 해결알고리즘은

1. 중위 순회, 후위 순회에 대한 정보를 저장합니다.

2. 후위 순회에서 루트 노드에 대한 정보를 저장합니다.

3. 중위 순회에서는 왼쪽 자식 노드와 오른쪽 자식 노드의 값을 얻습니다.

4. 위 과정을 반복하면서 루트노드의 값을 저장합니다.

5. 모두 반복한 이후 루트 노드의 값들을 순서대로 출력하면 전위 순회를 얻으실 수 있습니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 이용하여 중위, 후위 순회에 대한 정보를 저장하였습니다.
• 중위/후위 순회를 통해 전위 순회를 구하는 getPreOrder 재귀함수를 실행하였습니다.
• BufferedWriter에 전위 순회한 결과들을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• getPreOrder는 후위 순회에 값으로 루트 노드를 얻습니다.
• getPreOrder는 중위 순회에서는 왼쪽 자식 노드와 오른쪽 자식 노드를 얻습니다.
• getPreOrder는 루트 노드의 값들을 저장하여 전위 순회의 값을 얻습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main {
	static int N;
	static int[] inOrder, postOrder;
    //전위 순회 결과 저장 리스트
	static ArrayList<Integer> preOrder = new ArrayList<Integer>();
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	StringTokenizer st;
    	N = Integer.parseInt(br.readLine());
    	inOrder = new int[N];
    	postOrder = new int[N];
        //중위 순회 값 저장
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<N;i++) 
    		inOrder[i] = Integer.parseInt(st.nextToken());
    	//후위 순회 값 저장
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<N;i++)
    		postOrder[i] = Integer.parseInt(st.nextToken());
    	getPreOrder(0,N-1,0,N-1);	//전위 순회 구하는 함수 실행
    	for(int i=0;i<preOrder.size();i++) 		//전위 순회 값 BufferedWriter 저장
    		bw.write(preOrder.get(i) + " ");
    	
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //중위, 후위 순회값을 가지고 전위 순회 값 구하는 함수
    static void getPreOrder(int inS,int inE,int poS, int poE) {
    	if(inS<=inE && poS<=poE) {
        	int root = postOrder[poE];	//루트 노드 값
        	int pivot = 0;
        	preOrder.add(root);		//루트 값 전위 순회 값에 추가
        	for(int i=inS;i<=inE;i++) {
        		if(inOrder[i] == root) {
        			pivot = i;
        			break;
        		}
        	}
        	getPreOrder(inS, pivot-1, poS, poS + pivot - inS - 1);	//왼쪽 자식 노드
        	getPreOrder(pivot+1, inE,poS + pivot - inS , poE-1);	//오른쪽 자식 노드
    	}

    }
}