题目描述

根据先序遍历和中序遍历，计算出后序遍历

输入格式

第一行： 树的中序遍历

第二行： 同样的树的前序遍历

输出格式

单独的一行表示该树的后序遍历。

输入样例

ABEDFCHG
CBADEFGH

输出样例

AEFDBHGC

解法

误区

  1. 这道题一开始做的时候，准备先建树再后序遍历
  2. 求左右子树前序中序时，忘记了根节点的位置就相当于了左子串的长度，而不停的考虑没有左子树和没有右子树的条件，浪费了很多时间
  3. string.substr(start,length)中的第一个参数为索引，第二个参数为字符串长度，而不是终点的索引

代码

#include<iostream>
#include<string>

using namespace std;

void afterOrder(string midOrder,string preOrder){
     if(midOrder.size()==0)
           return;
     int leftLength=midOrder.find(preOrder[0]);
     afterOrder(midOrder.substr(0,leftLength),preOrder.substr(1,leftLength));
     afterOrder(midOrder.substr(leftLength+1,midOrder.size()-1-leftLength),preOrder.substr(leftLength+1,preOrder.size()-1-leftLength));
     cout<<preOrder[0];
     }

int main(){
    string mid,pre;
    cin>>mid>>pre;
    afterOrder(mid,pre);
    return 0;
    }