蓝桥杯算法训练VIP-FBI树

题目

题目链接

题解

递归。

很显然这是一棵满二叉树，对于二叉树，我一般喜欢用数组存储，对于根的编号为i的结点，其左儿子为2i，右儿子为2i+1。

建树的过程是深搜的过程，也称递归建树，先去建左右子树，最后建根，若左儿子和右儿子符号相等且不为‘F’，则根的符号与儿子符号相等，其他情况根的符号均为‘F’；边界条件，当递归到树的最后一层时，判断字符串（退化成一个字符了）为“0”还是“1”，为“0”则将该叶子结点的符号标记为“B”，否则为“I”，返回即可。

每个结点是什么符号都已经标记完成了，接下来就是输出，按后序遍历输出，既然建好树了，只要学过数据结构，写个后序遍历应该不是问题吧，就是先递归左右子树，再输出根，边界条件为到达叶子节点的儿子结点层，直接返回。

题目样例：

代码

#include
using namespace std;
const int N = 5000;

int n;
string str;
char tr[N];

void build(string s, int x, int dep) {
	if(dep == n) { // 到最后一层了 
		if(s == "0") tr[x] = 'B';  
		else if(s == "1") tr[x] = 'I';
		return ;
	}
	
	int m = s.size()/2; // 长度一半 
	build(s.substr(0, m), x