[NOIP2004]FBI树

傷城~ 2024-04-20 07:12 70阅读 0赞

⭐**简单说两句**⭐

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

题目： \[NOIP2004\]FBI树  ，哈哈，我们今天来看一道经典的二叉树题嘛，这是选自NOIP上的一道题，好了，我们一起来看看题意吧：

题目描述是复制的，可能有部分显示不对，我就把题目链接放下面！  
题目链接： [\[NOIP2004\]FBI树][NOIP2004_FBI]

### 题目描述 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16]

### 输入描述 ###

第一行是一个整数 N。

第二行是一个长度为 2N 的 01 串。

### 输出描述 ###

包含一行，这一行只包含一个字符串，即 FBI 树的后序遍历序列。

**示例1**

`输入`  
3  
10001011

`输出`  
IBFBBBFIBFIIIFF

`思路`:  
先放一张acwing y总画的图  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16 1]这道题差不多就是个二叉树遍历的模板题，只是需要加点判断  
具体的我们来看看代码吧！

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

#include<bits/stdc++.h>
    using namespace std;
    int n;
    string s;
    char deal(int l,int r){
        
        if(l==r){
        //只有一个节点时
            if(s[l]=='0'){
        cout<<'B'; return 'B';}
            else{
         cout<<'I'; return 'I';}
        }
        int mid=(l+r)>>1;
        char a= deal(l,mid);//递归处理左子树
        char b= deal(mid+1,r);//递归处理右子树
        if(a==b){
        //判断是B还是I
            if(a=='B'){
         cout<<'B';return 'B';}
            else if(a=='I') {
         cout<<'I';return 'I';}
        }
        cout<<'F';
        return 'F';
    }
    int main(){
        
        cin>>n;
        cin>>s;
        deal(0,(1<<n)-1);
        return 0;
    }

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

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

**结语**

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

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

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

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

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

[Link 1]: https://blog.csdn.net/m0_46833224
[NOIP2004_FBI]: https://ac.nowcoder.com/acm/problem/16660
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/5ebea83a64364641a5322744ed5001b2.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3EudGlhbmN4_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/b345b2cb948745b88cf4ab7b59f19ee3.png
[1caaf89f43f9c2ec5fdddccc50c08a6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/cf4502d9f6e84c4d9dc81e29e391ff1b.png