P1030 求先序排列

洛谷 树 C++ 所有文稿

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度\le 8≤8）。

输入输出格式

输入格式：

2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式：

1行，表示一棵二叉树的先序。

输入输出样例

输入样例#1：

BADC
BDCA

输出样例#1：

ABCD

思路

普通的先序遍历如下

void (int node){
    cout<<i;
    if (tree[i].left>0) xianxu(tree[i].left);
    if (tree[i].r>0) xianxu(tree[i].r);
    return;
}

在此基础上，加多一个根据中序和后序找出该节点的“代码块”即可

#include <iostream>
#include <string>
using namespace std;
string m,l;
void xian(char i,int in,int ml,int mr,int ll,int lr){
    cout<<i;
    /*left*/
    if(in>ml) xian(l[lr-(mr-in)-1],m.find(l[lr-(mr-in)-1]),ml,in-1,ll,lr-(mr-in)-1);
    /*right*/
    if(in<mr) xian(l[lr-1],m.find(l[lr-1]),in+1,mr,lr-(mr-in)-1,lr-1);
}
int main(){
    cin>>m>>l;
    xian(l[l.length()-1],m.find(l[l.length()-1]),0,m.length()-1,0,l.length()-1);
    return 0;
}

2019.3.26