洛谷 P1827 [USACO3.4]美国血统 American Heritage

画个图就很清楚了，用递归还原二叉树

#include<iostream>#include<cstdlib>#include<cstdio>#include<cstring> using namespace std;char pre[30],in[30];struct Node{char data;struct Node *lchild,*rchild;};struct Node *root;void combine(int l1,int r1,int l2,int r2,Node *&tree)//还原二叉树{if(l1>r1||l2>r2)return;int i,j;for(i=l1,j=l2;i<=r1;++i,++j){if(in[j]==pre[l1]) break;}tree=new Node;tree->lchild=NULL;tree->rchild=NULL;tree->data=pre[l1];combine(l1+1,i,l2,j-1,tree->lchild);//重复 combine(i+1,r1,j+1,r2,tree->rchild);}void postorder(Node *tree)//后序遍历{if(tree==NULL)return;postorder(tree->lchild);postorder(tree->rchild);cout<<tree->data;}int main(){scanf("%s%s",&in,&pre);getchar();//吸收空格 int len=strlen(pre);//计算节点个数 combine(0,len-1,0,len-1,root);//还原二叉树 postorder(root);//后序遍历 }