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

Tree Summing[UVA-112]

2024-09-25 22:13:39   214人阅读

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]


联系
我们