[C++]백준 4256번: 트리

문제 출처

풀이

재귀적으로 분할정복을 사용하였다. 전위 순회배열의 원소를 하나씩 보면서 중위 순회배열에서 해당 원소를 찾았고 그 원소의 위치보다 왼쪽에 있으면 left node, 오른쪽에 있으면 right node로 설정하였다.
다음은 전체 코드이다.

#include<iostream>
#include<vector>

using namespace std;

struct node {
	
	int key = 0;
	struct node *left = NULL;
	struct node *right = NULL;
	
	node(int _key, node *_left, node *_right) : key(_key), left(_left), right(_right){
		
	}
	node():key(1), left(NULL), right(NULL) {

	}
};

int idx = 0;	//전위 순회에서 살펴볼 idx이다.

node *makeTree(vector<int> &preorder, vector<int> &inorder, int start, int end) {
	
	int key = preorder[idx++];	//전위 순회 idx번째 원소를 key로 두고 idx를 +1한다.
	node *cur = new node(key, NULL, NULL); //node를 생성한다.
	int index;
    //start,end 범위 내에서 key에 해당하는 index를 찾는다.
	for ( index = start; index <= end; index++ ) {
		if ( inorder[index] == key )break;
	}
   	//index-1이 start보다 크거나 같다면, 즉 유효하다면 범위를 
    
    //start부터 index-1로 줄이고 left node를 재귀적으로 만든다.
	if ( index - 1 >= start ) {
		cur->left = makeTree(preorder, inorder, start, index - 1);
	}
    //left와 마찬가지이다.
	if ( index + 1 <= end ) {
		cur->right = makeTree(preorder, inorder, index + 1, end);
	}
    //left, right subtree를 모두 완성시키고 현재 node를 return한다.
	return cur;
}

void postOrder(node* head) {
	if ( head->left != NULL ) {
		postOrder(head->left);
	}
	if ( head->right != NULL ) {
		postOrder(head->right);
	}
	printf("%d ", head->key);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	for ( int i = 0; i < T; i++ ) {
		idx = 0;
		int n;
		cin >> n;
		vector<int> preorder(n);
		vector<int> inorder(n);

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

		node *head = makeTree(preorder, inorder, 0, n - 1);
		postOrder(head);
		printf("\n");
	}
	return 0;
}