题目内容

P1030

大意:给出一棵二叉树的中序和后序遍历,求其先序

解题思路

首先,前序遍历是左右根,中序是左根右,后序是左右根

所以可以发现后序遍历的最后一个必然是根,然后进行访问输出,再将中序和后序遍历分成两个独立的子树进行递归求解即可。

基本的思路如上,代码:

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

void dfs(string m,string b)
{
    if(!m.size())//如果递归完了就直接返回
        return;
    cout<<b[b.size()-1];//否则输出当前子树的根——后序遍历的最后一位
    int k=m.find(b[b.size()-1]);//然后将中序遍历的根找到,讲左右子树隔离开
    dfs(m.substr(0,k),b.substr(0,k));//递归求解左子树
    dfs(m.substr(k+1),b.substr(k,b.size()-k-1));//递归求解右子树
    return;
}

int main()
{
    ios::sync_with_stdio(false);//常规关闭流同步
    string m,b;
    cin>>m>>b;
    dfs(m,b);//开始遍历
    return 0;
}
最后修改日期:2020年3月1日

作者

留言

撰写回覆或留言

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