백준 2263 - 트리의 순회(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

중위 순회, 후위 순회의 특징을 알아야지 풀 수 있는 문제였습니다.

중위 순회의 특징은 부모 노드를 기준으로 왼쪽은 왼쪽 트리를 나타내고, 오른쪽은 오른쪽 트리를 나타냅니다.

후위 순회의 특징은 항상 마지막 수는 트리의 부모를 나타냅니다.

더 자세한 내용은 그림을 확인해주세요.

 

후위 순회와 중위 순회를 통해서 트리를 찾는 것은 확인했습니다. 이제 구현하는 단계가 남았습니다.

부모 노드가 중위 순회에서 어디 있는지 찾기 위해서는 위치를 기억하는 것이 필요합니다.

따라서 중위 순회를 입력받을 때, 해당 노드가 몇번째로 입력이 되었는지 같이 저장해줍니다.

 

• 전위 순회를 구하는 함수

void Find_pre_order(int In_start, int In_end, int post_start, int post_end) {
	if (In_start > In_end || post_start > post_end) return;
	int root_nood = Index[post_order[post_end]];
	int left_size = root_nood - In_start;
	int right_size = In_end - root_nood;
	cout << post_order[post_end] << " ";
	Find_pre_order(In_start, root_nood - 1, post_start, post_start + left_size - 1);
	Find_pre_order(root_nood + 1, In_end, post_start + left_size, post_end - 1);
}

전위 순회의 경우, 부모 노드부터 출력합니다.

따라서 부모 노드를 찾아줘야 합니다 -> 후위 순회의 마지막 수

또한 해당 노드가 중위 순회에서 몇번 째로 나타났는지를 확인합니다. -> root_nood

그렇다면 왼쪽 트리의 크기는, 중위 순회 시작값을 root_nood 길이에서 뺀 값이 됩니다. -> left_size

오른쪽 트리의 크기는, 중위 순회의 길이에서 root_nood를 뺀 값이 됩니다. -> right_size

 

왼쪽 트리, 오른쪽 트리를 찾았으니, 각 트리로 나누어서 해당 과정을 계속 반복해줍니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>

using namespace std;

int Index[100001];
int In_order[100001];
int post_order[100001];
int N;

void Find_pre_order(int In_start, int In_end, int post_start, int post_end) {
	if (In_start > In_end || post_start > post_end) return;
	int root_nood = Index[post_order[post_end]];
	int left_size = root_nood - In_start;
	int right_size = In_end - root_nood;
	cout << post_order[post_end] << " ";
	Find_pre_order(In_start, root_nood - 1, post_start, post_start + left_size - 1);
	Find_pre_order(root_nood + 1, In_end, post_start + left_size, post_end - 1);
}

void solve() {
	Find_pre_order(1, N, 1, N);
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &In_order[i]);
		Index[In_order[i]] = i;
	}
	for (int i = 1; i <= N; i++) {
		scanf("%d", &post_order[i]);
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요