首页 > 代码库 > Tree Summing[UVA-112]

Tree Summing[UVA-112]

Tree Summing

UVA-112 Time Limit:3000ms

这个题主要还是考察对二叉树的理解,刚看到感觉挺简单的,但是做起来却是一个接着一个坑。

首先说一下思路吧。最先想到的是重建整个二叉树,然后对整个树遍历,求出所有从树根到叶子的和,再与题目要求的数进行比较。后来一想其实没必要重建整个树,因为在这个题目的输入下,重建整个树的过程就相当于一次DFS,DFS到底实际上就是达到叶子节点了。因此,一边处理输入一边直接计算求和就行了,满足公式:$s_c=s_p+v_c$,其中$s_c$表示从根结点到当前结点的和,$s_p$表示从根结点到父节点的和,$v_c$表示当前结点存储的值。我这里是使用了栈进行非递归的求解,因此对应的栈顶元素就是$s_p$,其实很多解答用了递归也是非常精妙的,看起来非常简洁。

下面说说细节。第一个就是如何处理输入的问题。一组输入包含换行符和空格,因此fgets()和scanf()都不能用的,包括C++的cin.getline()。所以只能用getchar()来逐个字符读入,碰到不符合要求的就舍去。我这里是先将这个输入序列重新格式化后存储起来,然后调用solve()函数进行求解,实际上直接边读入边处理也是可以的,只是在叶子结点判断上要稍微麻烦一点。对于输入结束,因为题目保证数据合法,因此只要栈空,必然就应该结束当前数据的输入了。第二个是叶子结点的判断。注意题目的描述是,除了空树只包含一堆括号“()”,其余的,只要是叶子节点,必然在叶子节点的值的后面有两对括号(如:“(5()())”),因此要连续判断四个字符是不是一堆括号,来决定是不是叶子结点。对于我这种使用保存了的序列的,比较好操作,直接对数组的连续四个元素判断就行;如果是边读入边处理,那么就需要标志变量了,显然麻烦一些。最后一个坑,就是,输入数据可能包含负数!(虽然题目没给数据范围)。因为这个WA了好几遍,蛋疼。

最后是我的实现:

 1 #include<cstdio>
 2 #include<queue>
 3 #include<stack>
 4 using namespace std;
 5 char str[500000];
 6 int sum;
 7 int solve(const char * str)
 8 {
 9     if (str[0] == (&&str[1] == ))
10         return 0;
11     stack<int> st;
12     int i = 1, val, j = 0;
13     char buf[11];
14     for (; str[i] != (; i++, j++)
15         buf[j] = str[i];
16     buf[j] = 0;
17     sscanf(buf, "%d", &val);
18     st.push(val);
19     for (; !st.empty();)
20     {
21         if (str[i] == (&&str[i + 1] == ))
22         {
23             if (str[i + 2] == (&&str[i + 3] == ))
24             {
25                 if (st.top() == sum)
26                     return 1;
27                 i += 4;
28             }
29             else
30                 i += 2;
31         }
32         else
33         {
34             if (str[i] == ()
35             {
36                 i++;
37                 for (j = 0; str[i] != (; i++, j++)
38                     buf[j] = str[i];
39                 buf[j] = 0;
40                 i--;
41                 sscanf(buf, "%d", &val);
42                 st.push(st.top() + val);
43             }
44             else if (str[i] == ))
45                 st.pop();
46             i++;
47         }
48     }
49     return 0;
50 }
51 int main()
52 {
53     while (scanf("%d", &sum) != EOF)
54     {
55         stack<char> st;
56         getchar();
57         char c;
58         int pos = 0;
59         for (;;)
60         {
61             c = getchar();
62             if (c ==  ||c == \n)
63                 continue;
64             str[pos++] = c;
65             if (c == () st.push(c);
66             else if (c == ))st.pop();
67             if (st.empty())break;
68         }
69         str[pos] = 0;
70         if (solve(str))
71             printf("yes\n");
72         else
73             printf("no\n");
74     }
75     return 0;
76 }

 

Tree Summing[UVA-112]