THU2017spring 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
输入和输出的遍历序列均为[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"; } |
2021.07.17重写：
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 | #include <iostream> using namespace std; int n; int pre[500005], mid[500005]; bool flag; struct node { int v; node* l, * r; node(int v) :v(v), l(NULL), r(NULL) {} node(int v, node* l, node* r) :v(v), l(l), r(r) {} }; int findInMID(int v, int ms, int me) { for (int i = ms; i <= me; i++) if (mid[i] == v) return i; return -1; } node* build(int ps, int pe, int ms, int me) { if (ps > pe || ms > me)return NULL; if (ps == pe && ms == me) { if (pre[ps] != mid[ms])flag = true; return new node(pre[ps]); } int mm = findInMID(pre[ps], ms, me); if (mm == -1) { flag = true; return NULL; } return new node( pre[ps], build(ps + 1, ps + 1 + (mm - ms - 1), ms, mm - 1), build(ps + mm - ms + 1, pe, mm + 1, me) ); } void postTraversal(node* root) { if (!root)return; postTraversal(root->l); postTraversal(root->r); cout << root->v << " "; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; i++)cin >> pre[i]; for (int i = 0; i < n; i++)cin >> mid[i]; node* root = build(0, n - 1, 0, n - 1); if (flag)cout << -1; else postTraversal(root); } |