THU2017spring 2-3 Rebuild
描述
某二叉树的n个节点已经用[1, n]内的整数进行了编号。现给定该二叉树的先序遍历序列和中序遍历序列,试输出其对应的后序遍历序列。
输入
第一行为一个整数n。
第二、三行,即已知的先序、中序遍历序列,数字之间以空格分隔。
输出
仅一行。
若所给的先序、中续遍历序列的确对应于某棵二叉树,则输出其后序遍历序列,数字之间以空格分隔。否则,输出-1。
输入样例1
1
2
3 5
1 2 4 5 3
4 2 5 1 3
输出样例1
1 4 5 2 3 1
输入样例2
1
2
3 4
2 3 1 4
4 2 1 3
输出样例2
1 -1
输入样例3
1
2
3 8
5 2 4 1 3 6 7 8
4 2 1 5 3 7 6 8
输出样例3
1 4 1 2 7 8 6 3 5
限制
1 <= n <= 500,000
输入和输出的遍历序列均为[1, n]内整数的一个排列,整数间均以空格分隔。
时间:1 sec
空间:256 MB
提示
● 注意观察特殊节点在不同遍历序列中的位置
● 提示(.docx):
对应输入样例1的树结构:
先序遍历序列:12453
中序遍历序列:42513
注意到根节点就是先序序列的首元素,找到根节点后,根据根节点在中序序列中的位置,可划分出左右子树。
代码:(一个点TLE没过,其它都OK)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include<iostream> using namespace std; int n; int preorder[500005],inorder[500005]; enum Status{ OK=1, Node_Not_Exist=2, Value_Not_Equal=3 }; struct node{ int data; node * left; node * right; node(){ data=-1; left=NULL; right=NULL; } }; int findpos(const int * ptr,int start,int end,int value){//[start,end] for(int i=start;i<=end;i++){ if(ptr[i]==value)return i; } return -1; } Status MakeTree(int pre_start,int pre_end,int in_start,int in_end,node * cur){ cur->data=preorder[pre_start]; if(pre_start>pre_end||in_start>in_end)return Node_Not_Exist; if(pre_start==pre_end&&in_start==in_end){ if(preorder[pre_start]==inorder[in_start])return OK; else return Value_Not_Equal; } int _root_inorder_pos=findpos(inorder,in_start,in_end,cur->data); if(_root_inorder_pos==-1)return Value_Not_Equal; //重要! node * left=new node; node * right=new node; switch(MakeTree(pre_start+1,_root_inorder_pos-in_start+pre_start,in_start,_root_inorder_pos-1,left)){ case OK: cur->left=left; break; case Value_Not_Equal: return Value_Not_Equal; break; } switch(MakeTree(_root_inorder_pos-in_start+pre_start+1,pre_end,_root_inorder_pos+1,in_end,right)){ case OK: cur->right=right; break; case Value_Not_Equal: return Value_Not_Equal; break; } return OK; } void postorder(node * root){ if(root->left!=NULL)postorder(root->left); if(root->right!=NULL)postorder(root->right); cout<<root->data<<" "; } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++){ cin>>preorder[i]; } for(int i=1;i<=n;i++){ cin>>inorder[i]; } node * root=new node; if(MakeTree(1,n,1,n,root)==OK)postorder(root); else cout<<"-1"; } |