Hi.
I think that my solution is correct at least for the test I made, but the judge gives me 'wrong anwser'. Could you help me and show what kind of mistake I've made. The code is short and easy to understand:
#include <cstdio>
#include <deque>
#include <algorithm>
using namespace std;
struct Node
{
Node* left;
Node* right;
char c;
Node() : left(NULL), right(NULL), c('0') {}
};
char S[20004]; // S->sequence
Node* T; // T->tree
int Slen; // Slen->sequence length
void buildTree()
{
deque<Node*> Q; // Q -> queue
int Spos = 0; // Spos->sequence position
T = new Node();
Q.push_back(T);
while(!Q.empty() && Spos < Slen)
{
Node* n = Q.front();
Q.pop_front();
n->c = S[Spos++];
if(n->c == '1')
{
n->left = new Node();
n->right = new Node();
Q.push_back(n->left);
Q.push_back(n->right);
}
}
/* the tree for 110011000 looks like this:
1
/ \
1 0
/ \
0 1
/ \
1 0
/ \
0 0
*/
}
int count(Node* n, int sum)
{
if(n != NULL && n->c == '1')
{
++sum;
return max(count(n->left, sum), count(n->right, sum));
}
return sum;
}
int main()
{
for(int i = 0; i < 10; ++i)
{
scanf("%d%s", &Slen, S);
buildTree();
printf("%d\n", count(T, 0));
}
return 0;
}