청 화 데이터 구조 PA5 - 진 이 진 트 리 재 구성 (Proper Rebuild)

제목:https://dsa.cs.tsinghua.edu.cn/oj/problem.shtml?id=1146
제목 은 진 이 진 트 리 의 앞 순서 와 뒤 순 서 를 보 여 주 었 습 니 다. 이들 을 비교 하면 뿌리 노드 와 좌우 자 나 무 를 얻 고 재 귀 하면 됩 니 다.

#include
using namespace std;

struct node
{
	int data;
	node* lchild;
	node* rchild;
	node() :
		lchild(NULL), rchild(NULL) { }
	node(int e, node* lchild = NULL, node* rchild = NULL) :
		data(e), lchild(lchild), rchild(rchild) { }
};
void rebuild(node* root, int* pre, int* post, int n)
{
	if (n < 2)
	{
		return;
	}
	int postleft, preright;
	for (int i = 0; i < n; i++)
	{
		if (pre[i] == post[n - 2])
		{
			preright = i;
			break;
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (post[i] == pre[1])
		{
			postleft = i;
			break;
		}
	}
	root->lchild = new node(pre[1]);
	root->rchild = new node(post[n - 2]);
	rebuild(root->lchild, pre + 1, post, preright - 1);
	rebuild(root->rchild, pre + preright, post + postleft + 1, n - postleft - 2);
}

void trav(node* root) {
	if (!root) return;
	trav(root->lchild);
	printf("%d ", root->data);
	trav(root->rchild);
}

int main()
{
	int n;
	scanf("%d", &n);
	int* pre = new int[n];
	int* post = new int[n];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &pre[i]);
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &post[i]);
	}
	node* root = new node(pre[0]);
	rebuild(root, pre, post, n);
	trav(root);
}