1.题目描述：点击打开链接
2.解题思路：本题是训练二叉树的一道好题。首先要解决读数据问题，根据题意，当输入为“()”时，结束该组数据读入，当没有字符串时，整个输入结束。因此可以专门编写一个readin()函数，类型设置为bool型，遇到第一种情况时返回true，遇到第二种情况返回false，主程序中只要发现readin返回false时就break，结束整个大循环。
接下来要建立二叉树，首先为二叉树编写一个结构体，然后根据字符串的输入情况来建树，如果是‘L’就往左走，走不动时建一颗新树，同样的方法处理右子树，，最后读入结点值。由于输入可能有误，因此用一个全局变量failed来记录是否有输入错误的情况出现，如果在建树过程中发现该结点已经被赋过值，那么全局变量failed变为true。
最后开始BFS找结点值，此时可能出现有结点没有结点值的情况，因此要把bfs定义为bool型，只要出现这种非法情况，返回false。最后便不难根据情况进行输出了。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 256+10char s[N];struct Node{int v;bool have_value;Node*left, *right;Node() :have_value(false), left(NULL), right(NULL){}};Node*root;//根结点，使用前要申请空间bool failed;//记录输入是否有误Node*newnode(){ return new Node(); }void addnode(int v, char*s){int n = strlen(s);Node*u = root;for (int i = 0; i < n; i++)if (s[i] == 'L'){if (u->left == NULL)u->left = newnode();u = u->left;}else if (s[i] == 'R'){if (u->right == NULL)u->right = newnode();u = u->right;}if (u->have_value)failed = true;//已经赋过值了，说明输入有误u->v = v;u->have_value = true;//标记为已经赋值}bool readin()//读数据{failed = false;for (;;){if (scanf("%s", s)!=1)return false;//整个输入结束if (!strcmp(s, "()"))break;//读到结束标志，退出循环int v;sscanf(&s[1], "%d", &v);//读入结点值addnode(v, strchr(s, ',') + 1);//查找逗号，然后插入结点}return true;}bool bfs(vector<int>&ans)//利用bfs进行遍历，并将结点值放入vector中{queue<Node*>q;ans.clear();q.push(root);while (!q.empty()){Node*u = q.front(); q.pop();if (!u->have_value)return false;//没有结点值，返回falseans.push_back(u->v);if (u->left != NULL)q.push(u->left);if (u->right != NULL)q.push(u->right);}return true;}int main(){//freopen("t.txt", "r", stdin);while(1){root = newnode();if (!readin())break;vector<int>ans;if (!failed&&bfs(ans)){int len = ans.size();for (int i = 0; i < len; i++)printf("%d%c", ans[i], i == len – 1 ? '\n' : ' ');}else puts("not complete");}return 0;}
爱情使人忘记时间，时间也使人忘记爱情。
