本文最后更新于4 年前，文中所描述的信息可能已发生改变。
个人思路仅供参考，如有不足欢迎交流。
【问题描述】
二叉树是一种非常重要的数据结构，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，深度遍历有前序、中序以及后序三种遍历方法。
三种基本的遍历思想为：
前序遍历：根结点 —> 左子树 —> 右子树
中序遍历：左子树—> 根结点 —> 右子树
后序遍历：左子树 —> 右子树 —> 根结点
比如，求以下二叉树的各种遍历
前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
需要你编写程序解决的问题是：已知一个二叉树的前序遍历和中序遍历的结果，给出该二叉树的后序遍历的结果。
【输入形式】
有多组测试数据，每组测试数据三行，每组测试数据第一行只有一个正整数n，表示二叉树节点的数目，n=0意味着输入结束并且不需要处理。
每组测试数据第二行是二叉树的前序遍历的结果，是一个长度为n的字符串，每个节点由一个字符表示，字符是大小写英文字母及10个数字,不同的节点用不同的字符表示，也即无论前序遍历和中序遍历的字符串中没有重复的字符。
每组测试数据第二行是二叉树的中序遍历的结果，也是一个长度为n的字符串。
40%的测试数据1 ≤ n≤ 10；
30%的测试数据1 ≤ n≤ 20；
20%的测试数据1 ≤ n≤ 40；
10%的测试数据1 ≤ n≤ 62；
【输出形式】
对于每组测试数据，输出一行，是一个长度为n的字符串，表示二叉树后序遍历的结果。
【样例输入】
cpp
8
12457836
42758136
4
abcd
abcd
4
abcd
dcba
0【样例输出】
cpp
47852631
dcba
dcba【思路和做法】
- 前序遍历的开头一定是根结点；
- 在中序遍历中，根节点左侧一定是左子树，根节点右侧一定是右子树；
- 后序遍历的顺序是左子树->右子树->根结点；
- 提交代码（10/10分，C++）：
cpp
//35.二叉树遍历，从前序、中序到后序
#include <iostream>
using namespace std;
void getHou(string qian, string zhong)
{
if (qian.length() < 1) //限制
{
return;
}
string data = qian.substr(0, 1); //前序遍历的开头一定是根结点
string::size_type findData = zhong.find(data); //在中序遍历中找到根结点的位置
int posi = findData; //位置
//后序遍历：左子树->右子树->根结点
getHou(qian.substr(1, posi), zhong.substr(0, posi)); //遍历左子树
getHou(qian.substr(posi + 1), zhong.substr(posi + 1)); //遍历右子树
cout << data; //根结点
}
int main()
{
int n;
string qian, zhong;
while (cin >> n && n != 0)
{
cin >> qian >> zhong; //输入前序遍历、中序遍历
getHou(qian, zhong); //得到后序遍历的结果
cout << endl;
}
return 0;
}