[백준] 2263 - 트리의 순회

[문제링크]

2263번: 트리의 순회

 

0. postorder는 좌측 서브트리 - 우측 서브트리 - root이므로, 그 마지막 원소가 root이다

  - inorder는 좌측 - root - 우측 이므로, 위에서 구한 root 값을 찾음으로서 좌측/우측 서브트리의 크기를 구할 수 있다.

 

1. inorder의 시작과 끝, postorder의 시작과 끝 총 4개의 인덱스를 관리한다

 

2. root를 찾은 후 root - 좌 - 우 순서를 맞추기 위해

  - root를 출력문에 넣고

  - in/post의 시작점부터 좌측 서브트리의 길이만큼 인덱스를 구성해 재귀

  - in/post의 끝점부터 우측 서브트리의 길이만큼 인덱스를 구성해 재귀

 

3. 서브트리의 인자가 없으면 반환, 1개면 출력문에 삽입 후 반환한다

 

* 시간 향상을 위해, inorder의 index를 미리 생성해 사용할 수 있다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		
		int N = pint(br.readLine());
		inorder = new int[N];
		inorderIdx = new int[N+1];
		postorder = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < N; i++) {
			inorder[i]=pint(st.nextToken());
			inorderIdx[inorder[i]]=i;
		}
		st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < N; i++)postorder[i]=pint(st.nextToken());
		
		pre(0,N-1,0,N-1);
		
		System.out.println(sb);
	}
	static StringBuilder sb;
	static int[]inorder;
	static int[]inorderIdx;
	static int[]postorder;
	
	static void pre(int inS, int inE, int postS, int postE) {
		if(inS>inE)return;
		if(inE==inS) {
			sb.append(inorder[inS]).append(" ");
			return;
		}
		//post의 마지막 = 현재 서브트리의 root
		int root = postorder[postE];
		
		//root를 inorder에서 찾는다
		int cnt=inorderIdx[root];
		
		//root삽입
		sb.append(root).append(" ");
		//왼쪽
		pre(inS, cnt-1, postS, postS+(cnt-inS)-1);
		//오른쪽
		pre(cnt+1, inE, postS+(cnt-inS), postE-1);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면(Idx 유/무)