[백준] 2263 트리의 순회

1. 문제

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

2263번: 트리의 순회

2. 접근방법

중위순회와 후위순회를 보고 전위순회를 구하는 문제

위가 중위 아래가 후위

중위와 후위순회의 특성을 확인하면 전위순회를 구할 수 있다.

1. 후위 순회의 맨끝은 루트노드이다.

2. 중위 순회는 루트노드를 기준으로 왼쪽 서브트리, 오른쪽 서브트리로 나눌 수 있다.

3. 1,2의 특성을 이용해 분할정복으로 루트 출력 -> 왼쪽 서브트리 -> 오른쪽 서브트리를 반복한다.

4. 끝

 

3. 자바 코드

package Gold;

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

public class G3_2263트리의순회 {

	static int inOrder[], postOrder[], n;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		inOrder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		postOrder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		go(0,0,n);
		System.out.println(sb);
	}

	static void go(int inStart,int postStart, int size) {
		if(size <1)
			return;
		int root = postOrder[postStart+size-1];
		sb.append(root+" "); //중
		if(size == 1)
			return;
		int idx = 0;
		for(int i = inStart ; i < inStart+size; i++ ) {
			if(inOrder[i] == root) {
				idx = i;
				break;
			}
		}
		int preSize = idx-inStart;
		go(inStart,postStart,preSize); //좌
		go(inStart+preSize+1,postStart+preSize,size-preSize-1); //우
	}
}

4. 마치며

이전 전위 중위를 보고 후위순회를 찾는 문제와

비슷한 방식의 풀이였다.