当前位置：网站首页>根据前序中序求后序

根据前序中序求后序

2022-08-05 15:36:00 【-JMY-】

题目描述

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历。

输入

读入2个两个字符串，每个一行，长度均小于等于26。 
第一行为前序遍历，第二行为中序遍历。 
二叉树中的结点名称以大写字母表示：A，B，C....。

输出

输出一行，为后序遍历的字符串。

样例输入

ABC
CBA

样例输出

CBA

参考代码：

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int len;
int find(char x){
    for(int i=0;i<=len;i++)
        if(s2[i]==x)
            return i;
}
void pre(int l1,int r1,int l2,int r2){
    int ip=find(s1[l1]);
    if(ip>l2)pre(l1+1,l1+ip-l2,l2,ip-1);
    if(ip<r2)pre(ip-l2+l1+1,r1,ip+1,r2);
    cout<<s2[ip];
    return;
}
int main(){
    cin>>s1>>s2;
    len=s1.size()-1;
    pre(0,len,0,len);
    return 0;
}

原网站

版权声明
本文为[-JMY-]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qybcjmy/article/details/126177991

边栏推荐

猜你喜欢

随机推荐