数据结构 uva 112-Tree Summing
题目意思：用括号方式给你一颗二叉树，一个预期的值result，如果从根到叶子节点所有的节点的值的和能够等于result，则输出yes，否则输出no.
解题思路：
由于题目给的是有任意空格和回车，所以先把括号和数字全部存入到字符数组中，跳过空格和回车，然后再处理，借助栈的结构建一颗树，然后用dfs求解从根到叶子节点的sum值。
本题的关键是处理空树的情况，例如 0 （） 为no ; 5 (5()(1()())) 为 no ;
代码：
[cpp]
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;
struct NODE
{
int value;
int haveleft;
int left,right;
}tree[5500];
char save[5200];
int result,flag;
void DFS(int node,int sum)
{
if(flag==1)
return ;
sum+=tree[node].value;
if(tree[node].left==0) //到达了叶子节点
{
if(sum==result)
flag=1;
return ;
}
DFS(tree[node].left,sum);
if(flag==1)
return ;
if(tree[node].right)
DFS(tree[node].right,sum); //注意 5 (5()(1()())) 这种情况为假 ，wa了好几次
return ;
}
int main()
{
while(scanf("%d",&result)!=EOF)
{
memset(tree,0,5500*sizeof(struct NODE));
int cnt=0,tempcnt=0;
char c;
while((c=getchar())!='(') //清除空格和回车
;
save[cnt++]=c; //读入第一个可用字符
tempcnt++;
while(tempcnt) //括号匹配时结束
{
while((c=getchar())==' '||c=='\n') //去掉中间的空格和回车
;
if(c=='(') //注意括号处理机制
tempcnt++;
else if(c==')')
tempcnt--;
save[cnt++]=c;
}
save[cnt++]='\0';
if(save[0]=='('&&save[1]==')') //如果是空树，无论结果怎样都输出no,wa了好几次
{
printf("no\n");
continue;
}
stack<int>mystack; //记住二叉树的标号
int cur,num=0;
sscanf(&save[1],"%d",&cur); //去掉前括号后读入一个整数
num++; //二叉树的标号
mystack.push(num);
tree[num].value=cur; //树中的值
int len=1;
while(!mystack.empty())
{
for(;;len++) //跳过整数占用的字符
if(save[len]=='('||save[len]==')')
break;
if(save[len]=='('&&save[len+1]!=')') //读入一个整数
{
sscanf(&save[++len],"%d",&cur);
++num;
mystack.push(num); //把该树的标号放入栈中
tree[num].value=cur;
}
else if(save[len]==')'&&save[len-1]!='(') //出栈处理，建二叉树
{
int temp1,temp2;
temp1=mystack.top();
mystack.pop();
if(!mystack.empty()) //注意根的处理，要判断一下
{ www.zzzyk.com
temp2=mystack.top();
if(tree[temp2].haveleft==0) //如果左树已经没处理，处理左树
{
tree[temp2].left=temp1;
tree[temp2].haveleft=1;
