二叉树已知先序遍历+中序遍历求后序遍历

Knuth学徒

刚QQ上一个MM问我怎么写，其实就是个递归的问题，一般有两种解法，先根据先序遍历和中序遍历重新构造这棵树，然后对这棵树进行后序遍历，只是时间复杂度和空间复杂度都太高。

     第二种方法就是 纯递归，在读取先序和中序的同时输出后序遍历，这样效率很高。

    代码本来用C写的，但是例如 pre[30];这种太难看了……最近习惯用容器和模板库了.

1. 
   
2. /*
   
3. *************************
   
4. *     Auther:Knuth学徒
   
5. *     Lang : C++
   
6. *     Time : 2011-2-11
   
7. *************************
   
8. */
   
9. #include<iOStream>
   
10. #include<string>
    
11. #include<algorithm>
    
12. #include<cstdlib>
    
13. using namespace std;
    
14. 
    
15. void solve(string PreOrder, string InOrder)
    
16. {
    
17.         if(PreOrder.size()== 0 || InOrder.size() == 0 )
    
18.                 return ;
    
19.         char t = PreOrder[0]; //根节点
    
20.         int mid = InOrder.find(t);          //在中序遍历中找出根节点
    
21.         solve(PreOrder.substr(1 , mid) , InOrder.substr (0 , mid));  //分治
    
22.         solve(PreOrder.substr(mid+1,PreOrder.size() - 1- mid ) , InOrder.substr(mid+1 , InOrder.size()- 1- mid));
    
23. 
    
24.         cout<<t;  //输出后序遍历的根节点
    
25. }
    
26. 
    
27. int main()
    
28. {
    
29.        string Pre;
    
30.        string In;
    
31.        cin>>Pre>>In;
    
32. 
    
33.        solve(Pre,In);
    
34. 
    
35.        cout<<endl;
    
36.        return 0;
    
37. }
    
38. 
    
39. 
    

复制代码