2483: FBI树
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树,它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:
T的根结点为R,其类型与串S的类型相同;
若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历序列。
FBI树是一种二叉树,它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:
T的根结点为R,其类型与串S的类型相同;
若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历序列。
输入
第一行是一个整数N(0 ≤ N ≤ 10),第二行是一个长度为2N的“01”串。
输出
一行,这一行只包含一个字符串,即FBI树的后序遍历序列。
![](data:image/png;base64,R0lGODlhyACfAPcAAAAAAAAAMwAAZgAAmQAAzAAA/wArAAArMwArZgArmQArzAAr/wBVAABVMwBVZgBVmQBVzABV/wCAAACAMwCAZgCAmQCAzACA/wCqAACqMwCqZgCqmQCqzACq/wDVAADVMwDVZgDVmQDVzADV/wD/AAD/MwD/ZgD/mQD/zAD//zMAADMAMzMAZjMAmTMAzDMA/zMrADMrMzMrZjMrmTMrzDMr/zNVADNVMzNVZjNVmTNVzDNV/zOAADOAMzOAZjOAmTOAzDOA/zOqADOqMzOqZjOqmTOqzDOq/zPVADPVMzPVZjPVmTPVzDPV/zP/ADP/MzP/ZjP/mTP/zDP//2YAAGYAM2YAZmYAmWYAzGYA/2YrAGYrM2YrZmYrmWYrzGYr/2ZVAGZVM2ZVZmZVmWZVzGZV/2aAAGaAM2aAZmaAmWaAzGaA/2aqAGaqM2aqZmaqmWaqzGaq/2bVAGbVM2bVZmbVmWbVzGbV/2b/AGb/M2b/Zmb/mWb/zGb//5kAAJkAM5kAZpkAmZkAzJkA/5krAJkrM5krZpkrmZkrzJkr/5lVAJlVM5lVZplVmZlVzJlV/5mAAJmAM5mAZpmAmZmAzJmA/5mqAJmqM5mqZpmqmZmqzJmq/5nVAJnVM5nVZpnVmZnVzJnV/5n/AJn/M5n/Zpn/mZn/zJn//8wAAMwAM8wAZswAmcwAzMwA/8wrAMwrM8wrZswrmcwrzMwr/8xVAMxVM8xVZsxVmcxVzMxV/8yAAMyAM8yAZsyAmcyAzMyA/8yqAMyqM8yqZsyqmcyqzMyq/8zVAMzVM8zVZszVmczVzMzV/8z/AMz/M8z/Zsz/mcz/zMz///8AAP8AM/8AZv8Amf8AzP8A//8rAP8rM/8rZv8rmf8rzP8r//9VAP9VM/9VZv9Vmf9VzP9V//+AAP+AM/+AZv+Amf+AzP+A//+qAP+qM/+qZv+qmf+qzP+q///VAP/VM//VZv/Vmf/VzP/V////AP//M///Zv//mf//zP///wAAAAAAAAAAAAAAACH5BAEAAPwALAAAAADIAJ8AAAj/APcJHEiwoMGDCBMqXMiwocOHECNKnEixosWLGDNq3Mixo8ePIEOKHEmypMmTKFOqJKhspcuXMBW2XDgzps2bK2vu04mzp0+SYgAIHUr0p9GjG9EQXQoAqdOnE4UalAq1qtWEVAlOQnO1K1KdNamK4eq1rFemZtPirMlzH1qB9dTK/UkVDdm5eHtmzcu3ZNyBWf/u7UvYIzSWbpsSVDqU7MzDg/f9LUwZscGWQwce3jeJKJrJgDO33Vk5L0+eRSkuLbhZ8r7WpdVOjpua4N/RWEUPxB276mjImSeCLlh0uGTevY/qrF0z7mbkpBHWjp7c99TgBlsPh+6aOPbqZqc//1ScsN5m2AKnt+QO3uTMyeIhkq8Yv33O7Om/C2QPeGJb9faVdJp3kUG02XwYrWYZdQFWZBx1tOlnEYIP8aZggx9ZqB9/BgkWEoC7YRgRestJOFBczY1n0UwsXlegiBrVtx9rEVH4UVEtPQgjQyVG1mJC/NmokI7d5fbijuOZ6JGQHyqJpELxcdiQc26tJB5bT+bn5EawMUnShQVJWRZ3W3IEmpcllSmmV2uORFtPA2Z50HodoYemS0Ty9SNyvJkH0p0dIffXcyf21hlT3+mYJ0RtcglaUIgOhp5sLB0aqYibMXZpe5FlNelHi/oV2nX2RYbGJCaFaiWFp4bYW11ivNOkDGSNcgQreKiBeVKXLvX4Xa1ngQksRGfe9FZsn1K1FYNwpWqAsYotO+xTxh1ppUrV3qkqm6MeNChKgNZJ6kKf8qUpALFq5lK4Ip2bbn626elaS5AKlUmR1opbZUrmobhPvQDcK1hTfhaWL7zMisRuRwcnVtqLmw3sJnHrCmnnwlY13K1JGMe4sFDbVjUYmR3Tp9LIDGkMlbVEqnxRyRN62TLMsnq34L4hdkneexpN61CuN1MI9G3WISxdW8PtVS5UYXl5p4++5QsoVSFXiJIyUiNU/2J4QlM8p3c+xwQ1QeG6XLPDKSc5Y0b+4uzRTA137SraIs9H51RrF9Q23RjZOdJed3vt7bhh37hzh2TfLB3NCzGe8uF6Jy4fAFWn1PDSAi1t9kIe/vmxRJtnOK7CkE/rOGsSywe63PfxnTBNWtvMsGEoN94Q0Hmr1LRElUc3tmoawVdyuN+6/nqag6lKcO7xEp7R6bI3bztDEZOtWOFRhe726oVOdKBGwJlMH/QxI8hhU5iHiHuCz/96/EHsHpY0+atnpVP66b1MHv5Qts8k/+wqntEsdzDk0I93gnuZ9MLUvyeFCxq940/vmCc6piVEfqBbIOxeM8HMZWQ0NeGfWv/iVCTe7e9nQOre7SqSorZMC3smESFWujPBHM2Ngs0yCgTf55AdlgRgxzIJENFFEbhRZIgyStsRmXIXkGQiUkIR06TwNxNLLaVWMHsiFIFHkXMJ5V0eQVGnDugQwBGRi8TayRjRWLAakRFKFFoWAlWIn/l5R4Zro1lkJgFG1elvJK25lQIZ8qC9PBFV3TmfRA6kGDT0MSoJeuMCg4jG+l3xNYqboWp0Bck/GiZbSVQRCq3HFDDiEWZY42QGPQm+yVxMIHKc0CIHCI3OoKp3eoxWEysZkdR1cHK2Eo7xtNex1MUokiFJ5cYYtCZ2rU8gxDhjDg/iNwMtk336w+OUuuX/rtC0CVBtQaK9ePmQc3FlWDQb4i4rojNYeuaaoiwj+qzYmN0trVhp3Ec3S7jKiXhRmhaxY+PIEzLIwVFt08wddEhIk8Bg8iFEohJEcejGx/EQfsC8zOIYyELrWZShF9ymRj3qMYoOkGcbcZmnYpe9x82ncrzxIQ+psqZBRYijo1NXSu32NcxIEmF5cpkNK7qgMoWUpBrdHaiMhziPEo2jd9qaq3AXpJYujmZE6xT8AMAhMUGNSQWq1kRf1CM/8pNGfspKU6TKSvjkEG4vTR+79uJWDyJ1einUzGCEpFKClEug20sMzAJpI74SrHoNvOiLnMbVnHWPSdnSqWEjp8mM/+YPX9ojKa/sOsCGIGg7tJRcQpkqWcu6ZrKcrSxCLxu9XsITZ4A1aWCZ51DRPrRbfymkQl6Jr9ycFaMrHCAAJmXUg1oGrJ/z7Alt2yxGKnFI3kyg7PCHsb3qVLAxoyNPN0Ym5VKWtRt96H/Ko64CIVczQSVqf7aa3esyNp44JS14QXNTvCKEsNk5bxmDCzi3CQ+VMfgsePPWX9XedkYFXm98pdKyo6ZusxsN1ceup2ACbdKgFpXtbGOLt5BmjbyYpOuAW5tYmXQWZ880rXrte13sGpi9NxxxeDscXujMtbqhy6zGnkZQ4A60qRs8sYzv+mLc5Cuy3Lshb3z625HmUP94fqWxcQWY0eKhSWNPHa217jcqKUnIiD9ekZCdPONMsjR5Q34tfmBHtclhWGvW4jFFdPbS8WmztV5GJXvRUw8KN692vg3aR4MMGrjudJpgHlJm5UvHQKfWfCQeqEE7Z1wW51A3LW40A480tY4ptcQ0cjE/WSfqDL/4z569oPumWba1onq33yGUdy39WAxDRoNjFilzZZnaGh3YmrON9K5zKp3ujfe7cp6za74nkdHYSJukHi2NfwTfUUq3k2se3NfiW2FqZjIsIM6bWPP662tL28hWw6mQ2uJDCHPWOLiB90iZhBt045rbMm6jhE38XHxLO83Q7XaaJgrqf0dZtNt9OrauzY3t7xo8sIV+iDpVyKR/ooEYjUbQYSzeYFep00IImbiPC2JxjNOWo/98ZJpFzuVaMgWRDP9XpDBO3IPQcyj2LsjNhWJyKUfnnzBn+D/HOXKtMLHYCAH6rGNcaTWuc8DO2Us0VY6z8/Atmk8PtpoFvkysZZ3Ukrq2TPn/phMkhzrM3B226xZbZtJe+cqONho+4150GMtT22jnDAC+XuZDnpzi81FK0Av2drzr1513WU7e/W33pSfUgIiKePfofMm6a+mSINRgZNxNoKVEtNe5JjORw8xlrQt2KVn/VCpfzm9Sov7eNS4Ss7d69OvKlULGCWpUt256pdlSxYLHoKl34ndyERjuZXY5zAva4+bdXsWKp7vrZkNsRlf/d7890qLWCORCIr/peQ0rwO2nxhhY3nVYMz9CJmNolgBA/bddd2dBgznyY+0GdWdruQ2qf8QpQ4tEEXRcJxBDF0V1Vw8F2FgHZiPipIDmpgw3J4CLkoA9p3YiF2VMMkRU/ycQIsd5RvdyYKFgNTF0k4BS/YEeO1eCxTYpFpdpCJGCpVd1i1FKf3cQLShMIZZSz7ODg4RNvAYuKWU6PPiDPSg+AgJwvuaDREhOTDhWFzU7x6SERjiFS9hwIgFuUViEVGiFW9hPJ0E/ivFLpldtXNiEqgNDQAaFGnZqBHc65PNTIHFnHDOEXViGD6EdovJB2cZSrTciSMiHY8g5weOCgWJmQRZw1naICyR84YZ06QZ6v4RSmXc7mcBHBRcmkCIGjaIMjIEG1EZRLHIoYnAYIcgjmZAJG3g7mdhVknEYxHCKqah1yjCLsZQQ9HSJAxFNS2Fy45VlADgUFYh3A/GLPP+3W93jReoSMrpIFLwYOZNCjLSmd6H0Gp1xilKBJQOoRgqINQagIzaiizMBjo7ofttogGn4UNWoRYA4J+bIjd5ogwGji/ZVE0FRguS3eHmUENF0L7sRMCuoLlhTgVjDj0lzcNFUgftYbDMzeQ2RkP3Ij9P2Z3AHeSoWcwE2FX3kHCvQITdAIQCAf5t2EBdJHJp4frwXbCNJNo90awv2fdIHfnN3fXzVeAiDGjTpdvgYk6PHduDnKsl2d2xIdkIpY9wnZcakZpCFNuWCWgi2XcHmXLiIVCTDIIEkfYuVIsM0k5xFU11GYGVnMx0nk9LBftVHHCDVMO2XMEzSkXrzkePpiElBIVnw5zWgwZbuB5I+J1nNx3B2eSJuaXlQpm0/6XiPlRBPxI/rAQAYp3AE8UQY9xeOWYME4ZDQ5I8+liwu2ZiWmZiLyWpo52x82DBHiYFwxIuc5i1Ep4skkj+w4VMzoY4aJSQP9pbWY5pg5XDG8xiBiGascXOxUpBAwhQQmZdRt4vShmGrB4wZR02+SZv9uBTDKXQ0CFxYeYPeonR5GSaHooIxtl2ueCiZEDgPuBPbSYqOOBvYmZ27sZ1faVs1cXN8d0NDhCoy1BpouH4hIW97aFZy0p/++Z8AGqACOqAEWqAGeqA/ERAAOw==)
样例输入 复制
3
10001011
样例输出 复制
IBFBBBFIBFIIIFF