548 - Tree***
1798 ワード
/*
:
, 。
,
, 。
+1
*/
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <sstream>
using namespace std;
struct Node
{
Node *lchild,*rchild;
int v;
Node()
{
lchild=rchild=NULL;
v=0;
}
};
int inorder[10010],postorder[10010];
int result,value,min_value;
string a,b;
int len;
int init()
{
istringstream a_in(a);
istringstream b_in(b);
int temp;
len=0;
while(a_in>>temp)
inorder[len++]=temp;
len=0;
while(b_in>>temp)
postorder[len++]=temp;
return len;
}
int getPos(int c,int *t)
{
for(int i=0;i<len;i++)
if(c==t[i])
return i;
return 0;
}
Node *createTree(int n,int *t1,int *t2)
{
if(n<=0)
return NULL;
Node *root=new Node;
root->v=t2[n-1];
int pos=getPos(t2[n-1],t1);
root->lchild=createTree(pos,t1,t2);
root->rchild=createTree(n-pos-1,t1+pos+1,t2+pos);
return root;
}
void traverse(Node *root)
{
value+=root->v;
if(root->lchild==NULL && root->rchild==NULL)
{
if(value<min_value)
{
min_value=value;
result=root->v;
}
//In the case of multiple paths of least value you should pick the one with the least value on the terminal node.
// , 。
else if(value==min_value)
{
result=result<root->v?result:root->v;
}
}
if(root->lchild!=NULL)
{
traverse(root->lchild);
}
if(root->rchild!=NULL)
{
traverse(root->rchild);
}
value-=root->v;
// , value
}
int main()
{
//freopen("data.in","r",stdin);
while(getline(cin,a) && getline(cin,b))
{
int len=init();
Node *root=createTree(len,inorder,postorder);
min_value=1000000000;
value=0;
result=0;
traverse(root);
printf("%d
",result);
}
return 0;
}