Code: Select all
#include<iostream>
#include<sstream>
#include<vector>
using namespace std;
#define vi vector<int>
#define sz size()
#define pb push_back
#define imax 100000001;
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* rec(vi in,vi p)
{
if (in.sz==0)
return NULL;
int t;
bool flag=true;
for (int i=p.sz-1;i>=0 && flag;i--)
for (t=0;t<in.sz;t++)
if (p[i]==in[t])
{
flag=false;
break;
}
vi in1,in2;
for (int i=0;i<t;i++)
in1.pb(in[i]);
for (int i=t+1;i<in.sz;i++)
in2.pb(in[i]);
struct node* tmp =new node;
tmp->data=in[t];
// cout<<tmp->data<<endl;
tmp->left=rec(in1,p);
tmp->right=rec(in2,p);
return tmp;
}
int maxi;
int m,l;
void preorder(struct node* root)
{
// if (root==NULL)
// m=0;
if (root!=NULL)
{
m=m+root->data;
if (m<=maxi)
{
if (root->right==NULL && root->left!=NULL)
preorder(root->left);
else if(root->left==NULL && root->right!=NULL)
preorder(root->right);
else if (root->right!=NULL && root->left!=NULL)
{
preorder(root->left);
preorder(root->right);
}
else if (root->left==NULL && root->right==NULL)
{
//cout<<"sss\n";
if (m<maxi)
{
maxi=m;
// cout<<"max : "<<maxi<<endl;
l=root->data;
}
if(m==maxi && (root->data)<l)
{
l=root->data;
//cout<<"max : "<<m<<endl;
//cout<<"l : "<<l<<endl;
}
}
}
m=m-root->data;
}
}
int main()
{
string in,post;
while (getline(cin,in) && getline(cin,post))
{
vector<int> io,p;
istringstream iss(in);
char a[6];
string str;
while (iss>>str)
{
for (int i=0;i<str.size();i++)
a[i]=str[i];
a[str.size()]='\0';
int t;
t=atoi(a);
io.push_back(t);
}
istringstream ins(post);
while (ins>>str)
{
for (int i=0;i<str.size();i++)
a[i]=str[i];
a[str.size()]='\0';
int t;
t=atoi(a);
p.push_back(t);
}
m=0;l=10001; maxi=imax;
struct node *root;
root=rec(io,p);
preorder(root);
cout<<l<<endl;
}
return 0;
}
![:roll:](./images/smilies/icon_rolleyes.gif)