题意：
计算从根到叶节点的累加值，看看是否等于指定值。是输出yes，否则no。注意叶节点判断条件是没有左右子节点。
思路：
建树过程中计算根到叶节点的sum。
注意：
cin读取失败后要调用clear恢复，否则后面无法正常读取。
注意空树都要输出no
最初代码如下：
#include<cstdio> #include<cstring> #include<iostream> #include<string> #include<algorithm> #include<queue> #include<assert.h> using namespace std; int g_sum; bool ok; //build tree & dfs struct node { node(node* left=0, node* right=0, int value=0): l(left), r(right), v(value) {} node* l; node* r; int v; }*root; node* build_tree(int sum) { node* nd=0; char c; cin>>c; assert(c=='('); int v; if(cin>>v) { nd=new node; nd->v=v; //left nd->l=build_tree(sum+v); //right nd->r=build_tree(sum+v); if(!nd->l && !nd->r && (sum+v==g_sum)) { ok=true; } } else//空节点，没有int，从错误中恢复 { //if(sum==g_sum) // ok=true; cin.clear(); } cin>>c; assert(c==')'); return nd; } void bfs() { if(!root) return; queue<node*> q; q.push(root); while(!q.empty()) { node* nd=q.front(); q.pop(); cout<<nd->v<<" "; if(nd->l) q.push(nd->l); if(nd->r) q.push(nd->r); } } void delete_tree(node *root) { if(root) { delete_tree(root->l); delete_tree(root->r); } } int main() { while(cin>>g_sum) { ok=false; root=build_tree(0); //bfs(); delete_tree(root); if(ok) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }
可把显式的建树过程改为隐式的，不用建立node
#include<cstdio> #include<cstring> #include<iostream> #include<string> #include<algorithm> #include<queue> #include<assert.h> using namespace std; //注意空树都要输出no int g_sum; bool ok; //空节点返回0，非空返回1 int build_tree(int sum) { int empty=true; char c; cin>>c; assert(c=='('); int v; if(cin>>v) { empty=false; //left int left=build_tree(sum+v); //right int right=build_tree(sum+v); //叶节点：左右子节点都是空的 if(!left && !right) { // cout<<sum+v<<endl; if(sum+v==g_sum) ok=true; } } else//空节点，没有int，从错误中恢复 { cin.clear(); } cin>>c; assert(c==')'); return !empty; } int main() { while(cin>>g_sum) { ok=false; build_tree(0); if(ok) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }