题意：

给一棵点带权的二叉树的中序和后序遍历，找一个叶子使得它到根的路径上的权值的和最小，如果多解，那该叶子本身的权值应该最小

 

 

解题思路：

1.用getline()输入整行字符，然后用stringstream获得字符串中的数字  　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 2.用数组in_oder[]和post_order[]分别表示中序遍历和后序遍历的顺序，用数组rch[]和lch[]分别表示结点的左子树和右子树

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

3.用递归的办法根据遍历的结果还原二叉树(后序遍历的最后一个树表示的是根节点，中序遍历的中间一个表示根节点

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

4.二叉树构造完成后，再执行一次递归遍历找出最优解

 

#include<iostream> #include<string> #include<sstream> #include<algorithm> using namespace std; // 因为各个结点的权值各不相同且都是正整数，直接用权值作为结点编号 用数组存储二叉树 const int maxv = 10000 + 10; int in_order[maxv], post_order[maxv], lch[maxv], rch[maxv]; int n; bool read_list(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;}// 把in_order[L1..R1] 和 post_order[L2..R2]建成一棵二叉树， 返回树根 int build(int L1,int R1,int L2,int R2) {//最后的叶没有左右子树 如果有一个叶是5 则lch[5]=0 rch[5]=0 if(L1>R1) return 0;//空树 递归边界 int root=post_order[R2];// int p=L1;//找到根节点在中序排列中的位置 while(in_order[p]!=root) p++; int 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;//递归法 lch[2]=5,权值为2的左结点为5 }int best,best_sum;//目前为止的最优解和对应的权和 void dfs(int u, int sum) {sum += u;if(!lch[u] && !rch[u]) { // 叶子if(sum < best_sum || (sum == best_sum && u < best)) { best = u; best_sum = sum; }}if(lch[u]) dfs(lch[u], sum);if(rch[u]) dfs(rch[u], sum); }int main() {while(read_list(in_order)) {read_list(post_order);build(0, n-1, 0, n-1);best_sum = 1000000000;dfs(post_order[n-1], 0);cout << best << "\n";}return 0; }

 

转载于:https://www.cnblogs.com/is-Tina/p/7422485.html

总结

以上是生活随笔为你收集整理的算法入门经典第六章 例题6-8 树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。