题目1385：重建二叉树
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：4326
解决：1287
- 题目描述：
-
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并输出它的后序遍历序列。
- 输入：
-
输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为一个整数n(1<=n<=1000)：代表二叉树的节点个数。
输入的第二行包括n个整数(其中每个元素a的范围为(1<=a<=1000))：代表二叉树的前序遍历序列。
输入的第三行包括n个整数(其中每个元素a的范围为(1<=a<=1000))：代表二叉树的中序遍历序列。
- 输出：
-
对应每个测试案例，输出一行：
如果题目中所给的前序和中序遍历序列能构成一棵二叉树，则输出n个整数，代表二叉树的后序遍历序列，每个元素后面都有空格。
如果题目中所给的前序和中序遍历序列不能构成一棵二叉树，则输出”No”。
- 样例输入：
-
8 1 2 4 7 3 5 6 8 4 7 2 1 5 3 8 6 8 1 2 4 7 3 5 6 8 4 1 2 7 5 3 8 6
- 样例输出：
-
7 4 2 5 8 6 3 1 No
- 答疑：
- 解题遇到问题?分享解题心得?讨论本题请访问
- 这道题因为前序遍历第一个点就是根节点，中序遍历的中间某个点的左边就是左子树的，右边就是右子树的，这样算下来就可以用递归来做
-
#include<iostream> #include<vector> using namespace std; struct node { int val; node* left; node* right; node(int va):val(va),left(NULL),right(NULL){} }; vector<int> vec1; vector<int> vec2; //根据前序遍历中序遍历来构建二叉树 node* product(int a1,int b1,int a2,int b2) { node* root=new node(vec1[a1]);//当前根节点的创建 if(a1==b1) return root; int i=0; for(i=a2;i<=b2;i++) if(vec2[i]==vec1[a1]) break; if(i>a2) root->left=product(a1+1,a1+i-a2,a2,i-1);//左子树的创建 if(i<b2) root->right=product(a1+i-a2+1,b1,i+1,b2);//右子树的创建 return root; } //后序遍历二叉树 void last_out(node* root) { if(root->left!=NULL) last_out(root->left); if(root->right!=NULL) last_out(root->right); cout<<root->val<<' '; return; } int main() { int ary1[8]={1,2,4,7,3,5,6,8}; int ary2[8]={4,7,2,1,5,3,8,6}; for(int i=0;i<8;i++) vec1.push_back(ary1[i]); for(int i=0;i<8;i++) vec2.push_back(ary2[i]); node* root=product(0,7,0,7); last_out(root); }