题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=48
注意：1、有负数；2、空树答案为no.
版本一：
#include <iostream>
using namespace std;
bool proc_tree(int sum, int des, bool &chld)
{
char c;
int t;
bool lchld, rchld;
cin >> c;
if(cin >> t)
{
sum += t;
chld = true;
bool flag = proc_tree(sum, des, lchld) | proc_tree(sum, des, rchld); //此处若用||，可能会因为第一个操作数为真而不执行第二个操作数。
cin >> c;
if(!lchld && !rchld) return sum == des; //如果是叶子节点。
else return flag;
}
else
{
chld = false;
cin.clear();
cin >> c;
return false;
}
}
int main()
{
int des;
while(cin >> des)
{
bool chld;
cout << (proc_tree(0, des, chld) ? "yes" : "no") << endl;
}
return 0;
}
版本二：递归建树 + 搜索
#include <iostream>
using namespace std;
struct Node
{
int val;
int left, right;
Node(): left(-1), right(-1) {}
};
int cnt, des;
Node tree[10000];
int buildTree()
{
char c;
int t;
cin >> c;
if(cin >> t)
{
int tmp = ++cnt;
tree[tmp].val = t;
tree[tmp].left = buildTree();
tree[tmp].right = buildTree();
cin >> c;
return tmp;
}
cin.clear();
cin >> c;
return -1;
}
bool dfs(int idx, int sum)
{
if(idx == -1) return false;
sum += tree[idx].val;
if(tree[idx].left == -1 && tree[idx].right == -1)
{
return sum == des;
}
return dfs(tree[idx].left, sum) || dfs(tree[idx].right, sum);
}
void reset()
{
for(int i = 0; i <= cnt; ++ i)
{
tree[i].left = -1;
tree[i].right = -1;
}
}
int main()
{
while(cin >> des)
{
cnt = -1;
int head = buildTree();
cout << (dfs(head, 0) ? "yes" : "no") << endl;
reset();
}
return 0;
}
posted on 2011-11-24 21:50
wuxu 阅读(543)
评论(0) 编辑 收藏 引用 所属分类:
数据结构