-
Notifications
You must be signed in to change notification settings - Fork 0
/
uva00112.cpp
131 lines (125 loc) · 3.61 KB
/
uva00112.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
#define UNVISITED -1
#define POS_INF 1 << 25
#define NEG_INF -1 << 25
#define _ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(15);
using namespace std;
typedef long long int64;
typedef pair<int, int> ii;
/* Lesson learned:
1. If you can use system stack, for example, by doing recursion,
then use it! Don't make a stack<T> and mock the process by yourself.
You may easily make mistake about when to pop an element.
2. This situation is likely to appear while processing a tree.
In recursion, it would be better to just return some value for processing base cases.
Leave the complex logic judgement back to the non-base case calls. In another
word, try to process logic judgement only in the current layer, don't push
that judgement down to deeper recursions.
*/
// =============== Solution 1: build the tree explicitly ===============
// struct Node{
// Node(int _val): val(_val){}
// ~Node(){
// if(left) delete left;
// if(right) delete right;
// }
// int val;
// Node *left, *right;
// };
//
// class Tree{
// public:
// Tree(): root(NULL){}
// ~Tree(){
// if(root) delete root;
// }
//
// void build_tree(){
// root = build_node();
// }
//
// void inOrder(){
// inOrder(root);
// cout << endl;
// }
//
// bool find_sum(int target){
// if(root == NULL) return false;
// return find_sum(root, 0, target);
// }
// private:
// Node *build_node(){
// int val; char ch;
// cin >> ch;
// Node *node = NULL;
// if(cin >> val){
// node = new Node(val);
// node->left = build_node();
// node->right = build_node();
// } else {
// cin.clear();
// }
// cin >> ch;
// return node;
// }
//
// void inOrder(Node *node){
// if(node){
// inOrder(node->left);
// cout << node->val << " ";
// inOrder(node->right);
// }
// }
//
// bool find_sum(Node *node, int sum, int target){
// if(node == NULL) return false;
// if(node->left == NULL && node->right == NULL) return (sum + node->val) == target;
// else return(find_sum(node->left, sum + node->val, target) ||
// find_sum(node->right, sum + node->val, target));
// }
//
// private:
// Node *root;
// };
//
// int main(){ _
// int target;
// while(cin >> target){
// Tree tree;
// tree.build_tree();
// if(tree.find_sum(target)) cout << "yes" << endl;
// else cout << "no" << endl;
// }
// return 0;
// }
// =============== Solution 2: don't build the tree ===============
bool get_value(int target, int sum, bool &found){
int val; char ch; bool getValueSuccess = true;
cin >> ch;
if(cin >> val){
sum += val;
bool hasChild = false;
hasChild |= get_value(target, sum, found); //left child
hasChild |= get_value(target, sum, found); //right child
if(!hasChild) found |= (sum == target); //if has no children, judge if the target is found
} else {
getValueSuccess = false;
cin.clear();
}
cin >> ch;
return getValueSuccess;
}
bool find_sum(int target){
bool found = false;
get_value(target, 0, found);
return found;
}
int main(){ _
int target;
while(cin >> target){
bool found = false;
found = find_sum(target);
if(found) cout << "yes" << endl;
else cout << "no" << endl;
}
}