个人思路仅供参考,如有不足欢迎交流。

【问题描述】

二叉树是一种非常重要的数据结构,非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树,深度遍历有前序、中序以及后序三种遍历方法。

三种基本的遍历思想为:

前序遍历:根结点 —> 左子树 —> 右子树

中序遍历:左子树—> 根结点 —> 右子树

后序遍历:左子树 —> 右子树 —> 根结点

比如,求以下二叉树的各种遍历

二叉树

前序遍历: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的字符串,表示二叉树后序遍历的结果。

【样例输入】

8
12457836
42758136
4
abcd
abcd
4
abcd
dcba
0

【样例输出】

47852631
dcba
dcba

【思路和做法】

  • 前序遍历的开头一定是根结点;
  • 在中序遍历中,根节点左侧一定是左子树,根节点右侧一定是右子树;
  • 后序遍历的顺序是左子树->右子树->根结点;
  • 提交代码(10/10分,C++):
//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;
}