题意:给一棵带权树(每个节点权值为正且不相等)的中序和后序遍历,找一个叶子使得它到根的路径的权值尽可能小,如果有多解取叶子权值小的。输入中每两行代表一棵树,第一行为中序遍历第二行后序遍历。
分析:首先要搞清楚二叉树的先序(父左右)、中序(左父右)、后序(左右父)遍历的特点。后序遍历的最后一个字符就是根,然后坐在中序遍历中找到根,从而找出左右子树的节点列表,递归构造左右子树。而后再DFS遍历找最优解。
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int lch[maxn],rch[maxn],in_order[maxn],post_order[maxn],n;
int build(int L1,int R1,int L2,int R2){
if(L1>R1) return 0;//空树返回0;
int root=post_order[R2];
int cnt,p=L1;
while(in_order[p]!=root) p++;
cnt=p-L1;//左子树节点个数
lch[root]=build(L1,p-1,L2,L2+cnt-1);//递归构造左子树
rch[root]=build(p+1,R1,L2+cnt,R2-1);//递归构造右子树
return root;//返回根
}
int best,best_sum;
void dfs(int u,int sum){
sum+=u;
if(!lch[u]&&!rch[u]){//叶子
if(sum<best_sum||(best_sum==sum&&best>u)){
best_sum=sum;
best=u;
}
}
if(lch[u]) dfs(lch[u],sum);
if(rch[u]) dfs(rch[u],sum);
}
bool input(int *a){
string line;
if(!getline(cin,line)) return false;
stringstream ss(line);
int x;
n=0;
while(ss>>x) a[n++]=x;
return n>0;
}
int main(){
while(input(in_order)){
input(post_order);
build(0,n-1,0,n-1);
best_sum=1e9;
dfs(post_order[n-1],0);
cout<<best<<endl;
}
return 0;
}
原文链接: https://www.cnblogs.com/depth/p/5742136.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/238195
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!