剑指offer编程题—二叉树后序遍历

给定一个二叉树的前序遍历和中序遍历的序列，输出对应这个二叉树的后续遍历序列。
输入描述:

输入为一行。 两个字符串,分别表示二叉树的前序遍历和中序遍历结果,用空格分隔。保证数据合法

输出描述:

对应输出后序遍历序列

示例1

输入
ABDEC DBEAC
输出
DEBCA

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//由二叉树的中序遍历序列求其后续遍历序列
vector<char> postOrder(vector<char> &post,vector<char> pre,vector<char> in);
void display(vector<char> v);

int main(int argc,char **argv)
{
    string porder;
    string iorder;
    cin>>porder>>iorder;

    vector<char> pre(porder.begin(),porder.end());
    vector<char> in(iorder.begin(),iorder.end());

    vector<char> post;
    post=postOrder(post,pre,in);
    display(post);
    return 0;
}

//使用递归的思想完成解答，注意递归的出口
vector<char> postOrder(vector<char> &post,vector<char> pre,vector<char> in)
{
    if(pre.size()==0){
        return post;
    }
    if(pre.size()==1){
        post.push_back(pre[0]);
        return post;
    }

    int rootindex=0;
    int i;
    for(i=0;i<in.size();++i){
        if(in[i]==pre[0]){
            rootindex=i;
            break;
        }
    }
    vector<char> leftpre(pre.begin()+1,pre.begin()+rootindex+1);
    vector<char> leftin(in.begin(),in.begin()+rootindex);
    vector<char> rightpre(pre.begin()+rootindex+1,pre.end());
    vector<char> rightin(in.begin()+rootindex+1,in.end());

    post=postOrder(post,leftpre,leftin);
    post=postOrder(post,rightpre,rightin);
    post.push_back(pre[0]);
    return post;
}

void display(vector<char> v)
{
    int i;
    for(i=0;i<v.size();++i){
        cout<<v[i];
    }
}

运行结果：