由先序遍历和中序遍历回复树结构

元始天尊

动态规划法，找到左子树和右子树解即为整个树的解

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. #define min(x,y) ((x<y)?x:y)
   
5. #define arr(x,y) arr[(x)*size2+(y)]
   
6. 
   
7. struct NODE
   
8. {
   
9.         NODE* pLeft;
   
10.         NODE* pRight;
    
11.         char chValue;
    
12. };
    
13. 
    
14. NODE* tranverse(char* pre,int preb,int pree,char* in,int inb,int ine)
    
15. {
    
16.         NODE* father=new NODE();
    
17.         father->chValue=pre[preb];
    
18.         int i=inb;
    
19.         for(;i<=ine;i++)
    
20.         {
    
21.                 if(in[i] == pre[preb])
    
22.                         break;
    
23.         }
    
24.         father->pLeft=NULL;
    
25.         father->pRight=NULL;
    
26. 
    
27.         int l1=i-inb,l2=ine-i;//pre[preb+1,preb+l1]=>in[inb,inb+l1-1]  pre[preb-l2+1,pree]=>in[ine-l2+1,ine]
    
28.         if(l1>0)
    
29.         {
    
30.                 father->pLeft=tranverse(pre,preb+1,preb+l1,in,inb,inb+l1-1);
    
31.         }
    
32.         if(l2>0)
    
33.         {
    
34.                 father->pRight=tranverse(pre,pree-l2+1,pree,in,ine-l2+1,ine);
    
35.         }
    
36.         return father;
    
37. }
    
38. 
    
39. void Rebuild(char* pPreOrder,char* InOrder,int nTreeLen,NODE** pRoot)
    
40. {
    
41.         *pRoot=tranverse(pPreOrder,0,nTreeLen-1,InOrder,0,nTreeLen-1);
    
42. }
    
43. 
    
44. void main()
    
45. {
    
46.         NODE* root;
    
47.         Rebuild("abdcef","dbaecf",6,&root);
    
48.         cout<<root->chValue<<endl;
    
49. }
    

复制代码