首页 > 代码库 > 紫书p155 用中序后序构造二叉树
紫书p155 用中序后序构造二叉树
二叉树各节点权值是不相同的正整数,输入二叉树的中序后序,求到根节点权和最小的叶节点
紫书贼强,递归写的服气,慢慢理解吧
原文是建树之后用dfs搜的,我试着一边建树一边归纳最短路径
#include<bits/stdc++.h> using namespace std; const int maxv = 10010; int in[maxv], post[maxv], lch[maxv], rch[maxv];//中序,后序,左子树,右子树 int n, minnum, minsum; bool read(int* a)//读一行 { string line; if(!getline(cin, line)) return false; stringstream ss(line); n = 0; int x; while(ss >> x) a[n++] = x; return n > 0; } int build(int L1, int R1, int L2, int R2, int sum) { if(L1 > R1)//空树 return 0; int root = post[R2];//后序最后一个是根 int p = L1; while(in[p] != root) p++;//根在中序的位置 int cnt = p-L1;//左子树节点数 lch[root] = build(L1, p-1, L2, L2+cnt-1, sum+root);// rch[root] = build(p+1, R1, L2+cnt, R2-1, sum+root); if(lch[root] ==0 && rch[root] == 0)//树叶节点 { sum += root;//把叶节点加上 if(sum <= minsum) { minsum = sum; minnum = root; } } return root; } int main() { //freopen("in.txt", "r", stdin); while(read(in)) { read(post); minsum = 1e9; build(0, n-1, 0, n-1, 0); cout << minnum << endl; } return 0; }
紫书p155 用中序后序构造二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。