題目意思： 用括號方式給你一顆二叉樹，一個預期的值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.2cto.com temp2=mystack.top(); if(tree[temp2].haveleft==0) //如果左樹已經沒處理，處理左樹 { tree[temp2].left=temp1; tree[temp2].haveleft=1; } else //如果左樹已經處理，則處理右樹 tree[temp2].right=temp1; } } len++; } flag=0; DFS(1,0); //dfs計算結果 if(flag==1) printf("yes\n"); else printf("no\n"); } return 0; }
