来个C++的题解

解题思路:
以先序遍历为基础，找到root后在中序遍历中找root的位置并设置好范围len，变换pre和in数组的head指针

参考代码:

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

int read(){

int x=0,f=1;

char ch=getchar();

while(ch<'0'||ch>'9') {

if(ch=='-')

f=-1;

ch=getchar();

}

while(ch>='0' && ch<='9')

x=x*10+ch-'0',ch=getchar();

return x*f;

}

struct Node{

char data;

Node *lchild,*rchild;

};

void postOrder(Node *root)

{

if(root==NULL)

return;

postOrder(root->lchild);

postOrder(root->rchild);

cout<<root->data;

}

int find(char c,char *in,int len)

{

for(int i=0;i<len;i++)

if(in[i]==c)

return i;

return -1;

}

Node *msn(char *pre,char *in,int len)

{

if(len<=0)

return NULL;

Node *root=new Node;

int index=find(*pre,in,len);

root->data=*pre;

root->lchild=msn(pre+1,in,index);

root->rchild=msn(pre+index+1,in+index+1,len-index-1);

return root;

}

const int N=1000;

int main()

{

char *pre=new char[N],*in=new char[N];

cin>>pre;

cin>>in;

Node *root;

root=msn(pre,in,strlen(pre));

postOrder(root);

return 0;

}