백준 2263번 트리의 순회

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/2263

 

 

 

2263번: 트리의 순회

 

 

이번 문제는 재귀 알고리즘 문제였습니다.

 

 

중위 순회(In-Order) : 루트 노드 전까지 왼쪽 부분 트리이고 루트 노드가 나온 이후부터는 오른쪽 부분 트리

후위 순회(Post-Order) : 가장 마지막 노드가 루트 노드

 

 

각 순회마다 정점을 순회하는 순서는 다음과 같습니다.

 

✨ 전위 순회 : root -> left -> right

✨ 중위 순회 : left -> root -> right

✨ 후위 순회 : left -> right -> root

 

 

 

《문제 풀이》

 

1. 인오더와 포스트오더를 각각 배열에 입력

2. idx 배열에 인오더 배열의 인덱스를 순서에 맞게 저장  

3. 인오더와 포스트오더의 시작 정점, 끝 정점을 이용하여 preOrder( ) 수행

     (1) 포스트오더 배열의 끝은 루트 노드이므로 출력

     (2) 루트 노드의 왼쪽 서브 트리에서 preOrder( ) 수행

     (3) 루트 노드의 오른쪽 서브 트리에서 preOrder( ) 수행 

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define MAX 100001

using namespace std;

int n;
int inOrder[MAX], postOrder[MAX];
int idx[MAX]; 

void preOrder(int inBegin, int inEnd, int postBegin, int postEnd) {
	// 무한 출력 방지  
	if (inEnd < inBegin || postEnd < postBegin)
		return;
	
	// postOrder 배열의 끝은 루트 노드  
	int root = postOrder[postEnd];
	cout<<root<<" ";
	
	// left 
	preOrder(inBegin, idx[root] -1, postBegin, postBegin + (idx[root] - inBegin) - 1);
	// right
	preOrder(idx[root] + 1, inEnd, postBegin + (idx[root] - inBegin), postEnd - 1);
	
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n;
	
	for(int i=0; i<n; i++) 
		cin>>inOrder[i];
	
	for(int i=0; i<n; i++) 
		cin>>postOrder[i];
	
	// inOrder 배열의 인덱스 저장  
	for(int i=0; i<n; i++)
		idx[inOrder[i]] = i;
		
	preOrder(0, n-1, 0, n-1);
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면