AcWing 419. FBI树
原题链接
简单
作者:
王小强
,
2021-02-10 12:01:50
,
所有人可见
,
阅读 348
二叉树的遍历
#include <iostream>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char _val) : val(_val), left(nullptr), right(nullptr) {};
~TreeNode() {};
};
TreeNode* buildTree(const string& s, int l, int r) {
// recursion exit condition
if (l == r) // leaf node
return new TreeNode(s[l] - '0' ? 'I' : 'B');
int counts = 0; // [l, r] 左闭右闭区间内字符为‘1’的个数
for (int i = l; i <= r; ++i)
counts += s[i] == '1';
char type = 'F';
if (counts == 0) type = 'B';
else if (counts == r - l + 1) type = 'I';
auto root = new TreeNode(type);
int m = (l + r) >> 1;
root->left = buildTree(s, l, m);
root->right = buildTree(s, m + 1, r);
return root;
}
// postOrder traversal
void postOrder(TreeNode* root) {
if (!root) return;
postOrder(root->left);
postOrder(root->right);
printf("%c", root->val);
}
int n;
string s;
int main(void) {
cin >> n >> s;
postOrder(buildTree(s, 0, (1 << n) - 1));
}