本文共 1703 字，大约阅读时间需要 5 分钟。

2073

29.14%

552

85.69%

题目类型： 数据结构， 二叉树

输入与输出：

Sample Professor’s Trees      Corresponding Our Trees

左边的输入表示的是一棵树， 这棵树的一个结点可以有很多个儿子。所有的输入， 只要是可打印的字符，并且不是空格， ‘#’，’|‘， ’-‘的都是代表一个节点。

如果一个结点下方有‘|’则代表他有儿子。他的儿子们在一段连续‘-’的下面的结点。

如果用建树的方法，初看可能比较复杂， 但是其实是很并不难的。我的方法是构造一个有MAXN个儿子指针的结点， 然后开一个和最大的输入尺寸一样的二维数组存结点，分别相对应

于输入的二维字符串数组。

然后对输出进行枚举，当碰到一个是结点的字符时，就对结点数组相对应结点找儿子， 找儿子用一个函数实现， 向下搜索出它的所有儿子即可。

最后构造完之后， 对这棵树进行前序遍历输出， 注意输出左右括号的位置。

按理说这题只要并不难的，但是却被恶心到了， 昨天晚上开始做的，想好思路后很快就敲好代码，过了样例之后自信满满的提交了，然后，看到了血红血红的Wrong answer，给了我当头一棒。之后就不断的调试，不断的WA。 

然后就在网上找测试样例，结果发现也全部都可以过。这就说明一定不是我思路的问题， 肯定是一些细节或者边界条件没考虑到。

百度，谷歌被我翻了几十页，结果发现网上的解题报告全部都是用递归搜索解的，而且完全没有和我解题思路一样的。 更奇葩的是，我的队友也想了一个很奇葩的方法， 结果我们两个都卡了很久。

不断的WA，血淋淋的事实， 说明即使你认为自己是对的，确保是万无一失的， 也可能会有一些恶心的边界或者自己的思维漏洞而wa。

#include
   
    #include
    
     #include
     
      #include
      
       #define MAXN 205using namespace std;class Node{public:    char data;    Node *son[MAXN];};Node *root;Node node[210][210];char str[210][210];int row;inline bool isNode(char ch){    if(isprint(ch) && ch!='-' && ch!='|' &&            ch!=' ' && ch!='#')        return true;    return false;}void linkSon(int r, int c){    if(r+3 >= row || str[r+1][c]!='|') return;    int i,j;    // 移动到有 ‘-’ 的最左边    for(i=c; str[r+2][i]=='-'&&i>=0; --i) ;;    int sonNum=0;    i++;    // 从最左边的‘-’往右枚举到最右边的'-'.     //这里特别要注意边界条件，就因为这个i
       
        
         data); bool flag = true; for(int j=0; j
         
          son[j]!=NULL){ flag = false; if(j==0) printf("("); dfs(root->son[j]); } } if(flag) printf("()"); else printf(")"); }} void Solve(){ // 初始化 for(int i=0; i
         
        
       
      
     
    
   

转载地址：http://wyzni.baihongyu.com/