题目：
给定n个A和2n个B。用这些字符拼成一个字符串。要求这个串的全部前缀和后缀B的个数始终不少于A。
（一个字符串的前缀是仅仅从开头到某个位置为止的子串，后缀是仅仅从某个位置到结尾的子串）。
输入格式
多组数据。每组数据仅仅有一行，包括一个正整数n。
（n<=10^17)。
输出格式
每组数据输出一行，终于结果对99991取余数的结果。
分析：
简单的想法是建立一个二叉树。深度遍历一下就可以。
可是效率太低，对照较大的n不太适用，临时没想到什么好办法。先简单的做做看。
代码：
<span style="font-size:18px;">#include <stdio.h>
#include <stdlib.h> struct Node {
int value;
struct Node *left;
struct Node *right;
}; #define n 3
static int result = 0;
static int index = 0;
static int array[3 * n] = {0}; struct Node* initNode()
{
struct Node* temp = (struct Node *)malloc(sizeof(struct Node));
temp->value = 0;
temp->left = NULL;
temp->right = NULL;
return temp;
} void creatTree(struct Node* parent, int a, int b)
{
if (a > 0)
{
struct Node* left = initNode();
left->value = -1;
parent->left = left;
creatTree(left, a - 1, b);
}
if (b > 0)
{
struct Node* right = initNode();
right->value = 1;
parent->right = right;
creatTree(right, a, b - 1);
}
if (a <= 0 && b <=0)
{
return;
}
} //static int array[100] = {0}; void dfs(struct Node* root, int sum)
{
int i = 0;
if (root == NULL)
{
//result++;
return;
} if (root->value == 1 && root->left == NULL && root->right == NULL)
{
result++;
printf("%d\n", root->value);
printf("\nget one\n");
return;
} sum += root->value; if (sum < 0 || sum > n)
{
return;
}
else
{
printf("%d\n", root->value);
//index = 0;
dfs(root->left, sum);
dfs(root->right, sum);
} } void freeNode(struct Node* root)
{
if (root != NULL)
{
//printf("%d\n", root->value);
//printf("%d\n", root->left->value);
freeNode(root->left);
freeNode(root->right);
free(root);
}
return;
} int main()
{
int a = 0, b = 0, sum = 0;
a = n;
b = n * 2; /* 根节点 B */
struct Node *root = initNode();
root->value = 1; /* 建立二叉树 */
creatTree(root, a, b-1); /* 深度搜索遍历法得到结果 */
dfs(root, sum);
printf("result = %d\n", result); /* 释放内存 */
freeNode(root);
return 0;
}
</span>