THU2015 fall 2-3 Rebuild
描述
某二叉樹的n個節點已經用[1, n]内的整數進行了編号。現給定該二叉樹的先序周遊序列和中序周遊序列,試輸出其對應的後序周遊序列。
輸入
第一行為一個數n。
第二、三行,即已知的先序、中序周遊序列,數字之間以空格分隔。
輸出
僅一行。
若所給的先序、中續周遊序列的确對應于某棵二叉樹,則輸出其後序周遊序列,數字之間以空格分隔。否則,輸出-1。
輸入樣例1
5
1 2 4 5 3
4 2 5 1 3
輸出樣例1
4 5 2 3 1
輸入樣例2
4
2 3 1 4
4 2 1 3
輸出樣例2
-1
輸入樣例3
8
5 2 4 1 3 6 7 8
4 2 1 5 3 7 6 8
輸出樣例3
4 1 2 7 8 6 3 5
限制
1 <= n <= 500,000,n為整數
輸入和輸出的周遊序列均為[1, n]内整數的一個排列,整數間均以空格分隔。
時間:1sec
空間:256MB
代碼如下:
#include <stdio.h>
#include <stdlib.h>
const int SZ = 1 << 20; //提升IO buff
struct fastio{
char inbuf[SZ];
char outbuf[SZ];
fastio(){
setvbuf(stdin, inbuf, _IOFBF, SZ);
setvbuf(stdout, outbuf, _IOFBF, SZ);
}
}io;
#define N 500000
struct Node
{
Node *lchild, *rchild;
int x;
}Tree[N];
int loc;
//int pro[N], mid[N];
int count = 0;
Node *create()
{
Tree[loc].lchild = Tree[loc].rchild = NULL;
return &Tree[loc++];
}
Node *buildTree(int *pro, int *mid, int x1, int y1, int x2, int y2)
{
Node *root = create();
root->x = pro[x1];
int loc_root;
int flag = 1;
for (int i = x2; i <= y2; i++)
if (mid[i] == pro[x1]) //尋找樹根結點在中序序列中的位置
{
loc_root = i;
flag = 0;
count++;
break;
}
if (flag) return NULL;
if (loc_root != x2)
root->lchild = buildTree(pro, mid, x1 + 1, x1 + loc_root - x2, x2, loc_root - 1);
if (loc_root != y2)
root->rchild = buildTree(pro, mid, x1 + loc_root - x2 + 1, y1, loc_root + 1, y2);
return root;
}
void postOrder(Node *Tree)
{
if (Tree->lchild != NULL) postOrder(Tree->lchild);
if (Tree->rchild != NULL) postOrder(Tree->rchild);
printf("%d ", Tree->x);
}
int main()
{
int n;
scanf("%d", &n);
int *pro = (int *)malloc((n + 1) * sizeof(int));
int *mid = (int *)malloc((n + 1) * sizeof(int));
for (int i = 0; i < n; i++)
scanf("%d", pro + i);
for (int i = 0; i < n; i++)
scanf("%d", mid + i);
Node *Tree = buildTree(pro, mid, 0, n-1, 0, n-1);
if (count != n) printf("-1");
else postOrder(Tree);
printf("\n");
//system("pause");
free(pro);
free(mid);
return 0;
}