트리의 순회

문제

풀이

이 문제의 키포인트는 다음과 같다.
1. postorder는 left => right => root 순으로 항상 마지막에 root가 나온다.
2. inorder에서 left => root => right 순으로 root 기준으로 왼쪽은 left, 오른쪽은 right 이다.

이 키포인트를 중심으로 해결해야 한다.
1. postorder의 마지막 root를 기준으로 inorder에서 root 인덱스를 찾아야 한다.

int root = postorder[post_e];
		int root_idx = 0;

		for (int i = 0; i < N ; i++) {
			if (inorder[i] == root) {
				root_idx = i;
				break;
			}
		}

2. 구한 root 인덱스를 통해 inorder에서 left의 길이를 구한다.

int leftCnt = root_idx - in_s;

3. preorder 순서인 root => left => right 순서로 재귀호출한다.

sb.append(root).append(" ");
preorder(in_s, root_idx - 1, post_s, post_s + leftCnt - 1);
preorder(root_idx + 1, in_e, post_s + leftCnt, post_e - 1);

첫번째 preorder는 left를 나타내고
두번째 preorder는 right를 나타내고 있다.

코드

package algo;

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

public class main {
	
	static int N = 0;
	static int[] inorder;
	static int[] postorder;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("./input.txt"));
		//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		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());
		
		preorder(0, N - 1, 0, N - 1);
		System.out.println(sb.toString());
	}
	
	static void preorder(int in_s, int in_e, int post_s, int post_e) {
		if (in_s > in_e || post_s > post_e) return;
		
		int root = postorder[post_e];
		int root_idx = 0;
		
		for (int i = 0; i < N ; i++) {
			if (inorder[i] == root) {
				root_idx = i;
				break;
			}
		}
		
		int leftCnt = root_idx - in_s;
		sb.append(root).append(" ");
		preorder(in_s, root_idx - 1, post_s, post_s + leftCnt - 1);
		preorder(root_idx + 1, in_e, post_s + leftCnt, post_e - 1);
	}
}