[알고리즘] Java / 백준 / 트리의 순회 / 2263

[알고리즘] Java / 백준 / 트리의 순회 / 2263

문제

문제 링크

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

접근 방식

인오더와 포스트오더, 그리고 프리오더의 관계를 알면 풀 수 있는 문제이다.

인오더의 특징 : root 기준으로 왼쪽 노드들이 왼쪽 자식트리의 집합, 오른쪽 노드들이 오른쪽 자식트리의 집합

포스트오더의 특징 : 트리 배열의 마지막 값이 해당 트리의 root

1. 포스트오더 배열에서 현재 트리의 root를 찾고 stringbuilder에 저장한다.
2. 인오더 배열에서 root를 기준으로 왼쪽과 오른쪽으로 트리를 나눈다.
3. 1, 2를 반복하여 분할정복한다.

배열을 나눌 때 새로운 배열을 만들어 넘기면 메모리 초과가 나므로 인덱스를 활용한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2263 {
	
	static int[] in;
	static int[] post;
	static int[] inIdxArr;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		in = new int[n];
		post = new int[n];
		
		inIdxArr = new int[n+1];
		
		// 인오더 입력받기
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			in[i] = Integer.parseInt(st.nextToken());
			inIdxArr[in[i]] = i;
		}
		
		// 포스트오더 입력받기
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			post[i] = Integer.parseInt(st.nextToken());
		}
		
		sb = new StringBuilder();
		
		go(0, n-1, 0, n-1);
		
		System.out.print(sb);
	}
	
	static void go(int postStartIdx, int postEndIdx, int inStartIdx, int inEndIdx) {
		// 현재 루트 값 탐색
		int root = post[postEndIdx];
		sb.append(root+" ");
		
		// inorder에서 루트의 idx를 찾음 (idx기준으로 왼쪽은 왼쪽트리, 오른쪽은 오른쪽 트리이다.)
		int inRootIdx = inIdxArr[root];
		
		int leftTreeSize = inRootIdx - inStartIdx >= 0 ? inRootIdx - inStartIdx : 0;
		int rightTreeSize = inEndIdx - inRootIdx >= 0 ? inEndIdx - inRootIdx : 0;
		
		// 왼쪽 트리가 존재할 경우 왼쪽 트리의 post배열을 구해 in배열과 함께 왼쪽 트리를 탐색
		if(leftTreeSize > 0) {
			go(postStartIdx, postStartIdx+leftTreeSize-1, inStartIdx, inRootIdx-1);
		}
		
		// 오른쪽 트리가 존재할 경우 오른쪽 트리의 post배열을 구해 in배열과 함께 왼쪽 트리를 탐색
		if(rightTreeSize > 0) {
			go(postStartIdx+leftTreeSize, postEndIdx-1, inRootIdx+1, inEndIdx);
		}
		
	}

}