Tree UVA - 548
题意就是多次读入两个序列，第一个是中序遍历的，第二个是后序遍历的。还原二叉树，然后从根节点走到叶子节点，找路径权值和最小的，如果有相同权值的就找叶子节点权值最小的。
最后输出来叶子节点。
一开始写的时候是用gets读入的，报CE，
要用fgets写，关于fgets()，传送门:
一开始用bfs过的，后来发现，好多人都是dfs过的，又写了一下dfs。。。
代码:
//二叉树的中序和后序遍历还原树并输出最短路径的叶子节点值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const int inf=0x3f3f3f3f; struct node{
int l,r,val,father;
}tree[maxn]; int n=,minn,leaf;
int mid[maxn],beh[maxn]; int build(int la,int ra,int lb,int rb)
{
if(la>ra) return ;
int rt=beh[rb];
int p1=la;
while(mid[p1]!=rt) p1++;
int p2=p1-la;
tree[rt].l=build(la,p1-,lb,lb+p2-);
tree[rt].r=build(p1+,ra,lb+p2,rb-);
return rt;
} /*
int fa[maxn]; void bfs(int x)
{
queue<int> q;
vector<int> vec;
q.push(x);
fa[x]=0;tree[0].val=0;
while(!q.empty()){
int rt=q.front();q.pop();
if(rt==0){
break;
}
tree[rt].val=tree[fa[rt]].val+rt;
// cout<<tree[rt].val<<endl;
if(tree[rt].l){
fa[tree[rt].l]=rt;
q.push(tree[rt].l);
}
if(tree[rt].r){
fa[tree[rt].r]=rt;
q.push(tree[rt].r);
}
if(tree[rt].l==0&&tree[rt].r==0){
vec.push_back(rt);
} }
int l=vec.size();
int minn=inf,ans=inf;
for(int i=0;i<l;i++){
if(tree[vec[i]].val<minn){
minn=tree[vec[i]].val;
ans=vec[i];
}
if(tree[vec[i]].val==minn){
if(vec[i]<ans) ans=vec[i];
}
}
printf("%d\n",ans);
}
*/ void dfs(int rt,int sum)
{
sum+=rt;
if(!tree[rt].l&&!tree[rt].r){
if(sum<minn||(sum==minn&&rt<leaf)){
minn=sum;
leaf=rt;
}
}
if(tree[rt].l) dfs(tree[rt].l,sum);
if(tree[rt].r) dfs(tree[rt].r,sum);
} char c[maxn]; int main()
{
while(fgets(c,maxn,stdin)){
int l=strlen(c);
int i=,cnt=;
if(n==){
while(i<l){
if(c[i]=='\0') break;
if(c[i]==' '||c[i]=='\n') i++,mid[++n]=cnt,cnt=;
else{
cnt=cnt*+c[i]-'';
i++;
}
}
}
else{
n=;
while(i<l){
if(c[i]=='\0') break;
if(c[i]==' '||c[i]=='\n') i++,beh[++n]=cnt,cnt=;
else{
cnt=cnt*+c[i]-'';
i++;
}
}
build(,n,,n);
// bfs(beh[n]);
minn=inf,leaf=beh[n];
dfs(beh[n],);
printf("%d\n",leaf);
n=;
}
}
}