#include #include #include #include using namespace std; struct Node { int info; Node * left; Node * right; Node( int value, Node * llink, Node * rlink) : info(value), left(llink), right(rlink) { } }; bool hasSum(Node * root, int target) { if (root == 0) return false; if (root->left == 0 && root->right == 0){ return root->info == target; } else return hasSum(root->left, target - root->info) || hasSum(root->right, target - root->info); } Node * readTree(istream& input) { char ch; input >> ch; if (ch == '(') { input >> ch; if (ch == ')') return 0; int num; input.putback(ch); input >> num; Node *root = new Node(num, 0, 0); root->left = readTree(input); root->right = readTree(input); input >> ch; if (ch == ')') return root; else cout << "BAD! Looking for end paren" << endl; } else { cout << "BAD! should have been open paren" << endl; return 0; } } void print(Node * t) { if (t != 0){ cout << "("; cout << t->info << " "; print(t->left); cout << " "; print(t->right); cout << ")"; } else { cout << "() "; } } int main() { int num; Node * tree; while (cin >> num){ tree = readTree(cin); print(tree); if (hasSum(tree,num)){ cout << "yes" << endl; } else { cout << "no" << endl; } } }