C++ 백준_2263_"트리의 순회"

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

2263번: 트리의 순회

 

 

예전

전위, 중위 순회의 정보로 후위 순회하는 것을 배웠다.

​

그걸 이용하여 하려했다,

오랜만에 하려니 생각보다 복잡했지만

이전 배운 거를 기반으로 응용하였다.

​

​

​

​

먼저

preorder, inorder 정보로 하려면

​

preorder 제일 앞​​이 무조건 root(제일 꼭대기)가 된다

그럼 그 key 값과 inorder 정보 중

방금 구한 key 값이 같은 곳이 있다면

거기가 root 고

거기를 기준으로 좌우로 트리가 나눠진다.

​

그리고 preorder 두번째 값이

inoder 좌우로 나눈 것 중에

왼쪽 자식의 다시 root(제일 꼭대기)가 된다.

​

///

​

이런 정보로

postorder, inorder

는 반대로 하였다.

​

postorder의 제일 마지막 값이

tree 의 root가 된다.

​

그리고 postorder 의 뒤에서 두번째 값이

inorder 좌우로 나눈 것 중에

오른쪽 자식의 root가 된다.

​

이 정보로 tree를 아예 생성해서 순회하였다.

 

#include <iostream>
#include <vector>
using namespace std;

typedef struct node{
	int key;
	struct node* left_link;
	struct node* right_link;
}node;

int n;
int inorder[100000];
int postorder[100000];

int post_idx;

node* make_tree(int start, int end) {
	if (start > end) return NULL;
	node* N = (node*)malloc(sizeof(node));

	N->key = postorder[post_idx--];
	N->left_link = N->right_link = NULL;
	
	if (start == end) return N;

	int mid = 0;
	for (; mid < n; mid++) {
		if (N->key == inorder[mid])
			break;
	}

	N->right_link = make_tree(mid + 1, end);
	N->left_link = make_tree(start, mid - 1);
	return N;
}

void preorder(node* root) {
	if (root) {
		cout << root->key << " ";
		preorder(root->left_link);
		preorder(root->right_link);
	}
}

int main(void) {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	post_idx = n - 1;

	for (int i = 0; i < n; i++) {
		cin >> inorder[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> postorder[i];
	}


	node *root = make_tree(0,n-1);
	
	
	preorder(root);

}