求先序排列

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例 #1：

BDCA

输出样例 #1：

ABCD

代码

#include <bits/stdc++.h>
using namespace std;

char a[15],b[15];

void dfs(int i1,int j1,int i2,int j2){
    if (i1>j1||i2>j2) return;
    if (i1==j1){
        cout<<a[j1];
        return;
    }
    cout<<b[j2];
    for (int k=i1;k<=j1;++k){
        if (a[k]==b[j2]){
            dfs(i1,k-1,i2,j2-j1+k-1);
            dfs(k+1,j1,i2+k-i1,j2-1);  //注意
            return;
        }
    }
}

int main(){
    cin>>a+1;
    cin>>b+1;
    dfs(1,strlen(a+1),1,strlen(a+1));
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/19/