由中序和后序重建二叉树
总时间限制： 500ms内存限制： 65535kB
说明
我们知道如何按照三种深度优先顺序在一棵二叉树中旅行，得到中根序列、前根序列和后根序列。 相反，只要给出二叉树的中根序列和后根序列，或者给出中根序列和前根序列，就可以重构一二分树。 本问题要求输入一个二叉树的中根序列和后根序列，在内存中重构二叉树，最后输出这个二叉树的前根序列。
用不同的整数唯一识别二叉树的各个节点，下面的二叉树
中根序列为9 5 32 67
后根序列9 32 67 5
上一根序列5 9 67 32
输入
两行。 第一行是二叉树的中根序列，第二行是后根序列。 每个数字表示的节点之间用空格分隔。 节点的数字范围为0到0~65535。 暂时不需要考虑不合理的输入数据。
输出功率
一行。 由输入中根序列和后根序列构成的二叉树的前根序列。 每个数字表示的节点之间用空格分隔。
样本输入
9 5 32 67
9 32 67 5
样本输出
5 9 67 32
想法：
根据后序序列根节点位于最后的特性确定根节点，再根据中序序列根节点的左侧为左部分树、右侧为右部分树的特征重构二叉树，并按照先序序列输出即可。 (记得释放二叉树() )。
# includeiostreamusingnamespacestd； typedef struct _btn{int data； struct _btn *lchild； struct _btn *rchild； (BTN； # define maxn 65536 inti norder [ maxn ]； int postOrder [MAXN]； BTN *构建树(intio 1、int io2、int po1、int po2 ) /中序的首尾元素坐标、后序的首尾元素坐标({int iolen=io2-io1 1； //中序长度int i； btn *root=new btn； //将新创建的一个节点作为根节点root-data=postOrder[po2]； //后序的最后一个元素是根节点root-lchild=NULL； 根字符=空值； //左右孩子初始化为空//中序查找根节点for (I=0； iiolen； I ) if (根数据==in order [ io1i ] ) break； (//于是左子树的中序关注io1至io1 i-1，后序关注po1至po1 i-1 ) /递归出口，只有在io1=io1 i-1，即i=1时，语义if(I=1)根液晶=buot-lchild=but //返回根节点返回根路由； }voidpreorder(BTN*root ) if ) root！=null}{coutroot-data ' '； preorder (根液晶)； preorder (根循环)； (//二叉树的语音根)为了释放BTN *根) if (根)，以后进行遍历=空(删除树(根)； 删除树(根循环)； 删除根； 根=空； } } int main () { int i=0； while(CiniNorder[I] ) if(CIN.get )！=' ' ) break； (I=0； while(CINpostorder[I] ) if(CIN.get )！=' ' ) break； } BTN * root=构建树(0，I-1，0，I-1 )； reorder (根)； elete tree (根)； 返回0； }