题目内容

P1827

给定一二叉树的中序和先序遍历,求后序遍历

解题思路

与求先序排列的类似,思路都是找根然后递归求解。

注意到一个子树的先序遍历的第一个元素必然是这棵子树的根,因此可以通过在中序遍历中查找这个根来获知左右子树的大小然后分开递归左右子树

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

void dfs(string f,string m)
{
    if(f.empty())
        return;
    int k=m.find(f[0]);
    dfs(f.substr(1,k),m.substr(0,k));
    dfs(f.substr(k+1,f.size()-k),m.substr(k+1));
    cout<<f[0];
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    string f,m;
    cin>>m>>f;
    dfs(f,m);
    return 0;
}
最后修改日期: 2020年3月28日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。