uva 548 - Tree - dblank

# uva 548 - Tree

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000 + 10, Mod = 1000000009;
typedef long long ll;
char s[N];
int post[N], in[N], minx, ans;
struct treenode
{
treenode *left;
treenode *right;
int data;
};
treenode build(int post, int *in, int len)
{
if(len == 0)
{
return NULL;//子树建立完毕，返回空
}
treenode *node = new treenode;//新的节点
int id  = 0;
for(; id<len; id++)
{
if(in[id] == post[0])//在中序遍历中找到根节点的位置
break;
}
node->data = post[0];
//  cout<<node->data;//输出结果为前序
node->left = build(post+len - id, in, id);//建立左子树
node->right = build(post+1, in+id+1, len - (id+1));//建立右子树
return node;//返回该节点
}
void dfs(treenode *root, int sum)
{
sum += root->data;
if(root ->left == NULL && root->right == NULL)
{
//  cout<<root->data<<endl;
if(sum<minx)
{
minx = sum;
ans = root->data;
}
if(sum == minx && root->data < ans)
{
ans = root->data;
}
return ;
}
if(root->left != NULL)
dfs(root->left, sum);
if(root->right != NULL)
dfs(root->right, sum);
}
int main()
{
while(gets(s))
{
int len = strlen(s);
int k1 = 0, k2 = 0, num = 0;
for(int i = 0; i<=len; i++)
{
num = 0;
while(isdigit(s[i]))
{
num = num * 10 + s[i] - '0';
i++;
}
in[k1++] = num;
}
gets(s);
len = strlen(s), num = 0;
for(int i = 0; i<=len; i++)
{
num = 0;
while(isdigit(s[i]))
{
num = num * 10 + s[i] - '0';
i++;
}
post[k2++] = num;
}
ans = inf;
minx = inf;
reverse(post, post+k2);//倒转遍历结果，更加好处理
treenode *root = new treenode;
root = build(post, in, k2);
dfs(root,0);
printf("%dn", ans);
}
return 0;
}