[NOIP2001]求先序排列

迈不过友情╰ 2024-04-20 07:12 71阅读 0赞

⭐**简单说两句**⭐

> **作者：****后端小知识**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

题目： \[NOIP2001\]求先序排列  ，哈哈，我们今天来看一道二叉树的递归题嘛，这是选自NOIP上的一道题，好了，我们一起来看看题意吧：

题目描述是复制的，可能有部分显示不对，我就把题目链接放下面！  
题目链接： [\[NOIP2001\]求先序排列][NOIP2001]

### 题目描述 ###

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

### 输入描述 ###

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

### 输出描述 ###

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

**示例1**

`输入`

> BADC  
> BDCA

`输出`

> ABCD

`思路`:

> 总体思路就是递归的处理左子树和右子树，代码里面有注释！

`我们来看看成功AC的代码吧：`

#include<bits/stdc++.h>
    using namespace std;
    string zhong,hou;
    void deal(int l1,int r1,int l2,int r2){
        //l1到r1的中序遍历，  l2到r2的后序遍历
        if(l1>r1||l2>r2) return ;
        cout<<hou[r2];
        int pos=-1;
        for(int i=0;i<=r1;i++) if(zhong[i]==hou[r2]) pos=i;
        deal(l1,pos-1,l2,l2+pos-1-l1);//先看左子树
        deal(pos+1,r1,r2-r1+pos,r2-1);//看右子树
    }
    int main(){
        
        cin>>zhong>>hou;
        int len=hou.length();
        deal(0,len-1,0,len-1);
        return 0;
    }

【都看到这了，点点赞点点关注呗，爱你们】??

![抽象工厂  引导关注][1caaf89f43f9c2ec5fdddccc50c08a6c.png]

**结语**

`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!???

**作者：****后端小知识**

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

?欢迎关注?点赞?收藏⭐️留言?

[Link 1]: https://blog.csdn.net/m0_46833224
[NOIP2001]: https://ac.nowcoder.com/acm/problem/16692
[1caaf89f43f9c2ec5fdddccc50c08a6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/227ecaaec5c5433c9c8f7e9153ca6c5f.png