UVA 122(フォークツリー+文字列入力)
2007 ワード
件名:
一本の二叉の木の上のいくつかのノードの値(全部正数)をあげて、ルートからすべての所与の点までの経路上のノードに値があるかどうかを判断して、一回だけ与えられます.
この問題は難しくないです.主に細かいところの処理です.勉強してください.
一本の二叉の木の上のいくつかのノードの値(全部正数)をあげて、ルートからすべての所与の点までの経路上のノードに値があるかどうかを判断して、一回だけ与えられます.
この問題は難しくないです.主に細かいところの処理です.勉強してください.
#include
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int maxn=200005;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
struct node
{
int v;
bool have_value;
node *left,*right;
node():have_value(false),left(NULL),right(NULL) {}
};
node *root;
bool fail;
node *newnode()
{
return new node();
}
char s[1000];
void addnode(int v,char *s)
{
int n=strlen(s);
node *u=root;
for(int i=0; ileft==NULL)
{
u->left=newnode();
}
u=u->left;
}
else if(s[i]=='R')
{
if(u->right==NULL)
{
u->right=newnode();
}
u=u->right;
}
}
if(u->have_value)
fail=true;
u->v=v;
u->have_value=true;
}
bool read()
{
fail=false;
for(;;)
{
if(scanf("%s",s)!=1) return false;
if(!strcmp(s,"()")) break;
int v;
sscanf(&s[1],"%d",&v);
addnode(v,strchr(s,',')+1);
}
return true;
}
bool bfs(vector &ans)
{
queue q;
ans.clear();
q.push(root);
while(!q.empty())
{
node *u=q.front();
q.pop();
if(!u->have_value) return false;
ans.push_back(u->v);
if(u->left)
q.push(u->left);
if(u->right)
q.push(u->right);
}
return true;
}
int main()
{
while(1)
{
root=newnode();
if(!read())
break;
vector ans;
if(!fail&&bfs(ans))
{
int len=ans.size();
for(int i=0; i