二叉树由前序遍历和中序遍历求后序遍历

题目：二叉树遍历

问题描述

给定一棵二叉树的先序遍历和中序遍历序列，求其后序遍历序列。

输入格式

输入数据有两行，为两个字符串，其长度n均小于等于26。第一行为先序遍历序列，第二行为中序遍历序列。

二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出格式

在一行上输出后序遍历序列。

样例输入

ABC

BAC

样例输出

BCA

1 #include <iostream>
 2 #include <string>
 3 using namespace std ;
 4 void backvis(string pro,string mid)
 5 {
 6     if(pro.length()==0)//边界条件，当字符串为空的时候表示遍历空树
 7     return;
 8     else if(pro.length()==1)//边界条件，当字符串只有一个字母的时候表示树只有一个节点，后序遍历序列即该节点本身
 9     {
10         cout<<pro[0];    
11         return;    
12     }
13 
14     int k=0;//k表示根节点在中序遍历中的位置,从0开始
15     char root=pro[0];
16     for(int i=0;i<mid.length();i++)
17     {
18         if(mid[i]==root)
19         k=i;    
20     }
21     
22     backvis(pro.substr(1,k),mid.substr(0,k));//依据左子树的先序遍历和中序遍历得到左子树后序遍历序列
23     backvis(pro.substr(k+1),mid.substr(k+1));
24     cout<<root;
25 }
26 int main()
27 {
28    string pro,mid;
29    cin>>pro>>mid;
30    backvis(pro,mid);
31     return 0;
32 }