题意：给出一颗点带权的二叉树的中序和后序遍历，找一个叶子使得它到根的路径上的权和最小。
学习的紫书：先将这一棵二叉树建立出来，然后搜索一次找出这样的叶子结点
虽然紫书的思路很清晰= =可是理解起来好困难啊啊啊啊
后来终于问懂一丢丢了---
比如说样例：
中序遍历：3 2 1 4 5 7 6
后序遍历：3 1 2 5 6 7 4
首先做第一层： 在后序遍历中的最后一个数为根节点，然后在到中序遍历中找到这个根节点，在这个根节点的左边是左子树，右边是右子树，这样就确定出了左子树和右子树的区间
然后做第二层 中序遍历左子树的长度等于后序遍历中左子树的长度 即为在这个样例中：
中序遍历的左子树为 3 2 1 后序遍历的左子树为3 1 2 然后又可以确定2为这颗左子树的一个根节点，又可以将 3 2 1划分成左右子树区间
就这样一层一层划分建树
概括一下就是：
中序遍历序列：【左子树区间中序遍历序列】【根】【右子树区间中序遍历序列】
后序遍历序列：【左子树区间中序遍历序列】【右子树区间中序遍历序列】【根】
话说build函数也理解了好久的说 = =
对于lch[root]=build(L1,p-1,L2,L2+cnt-1);L1到p-1是在中序遍历中的左子树 L2到L2+cnt-1是在后序遍历中的左子树
对于rch[root]=build(p+1,R1,L2+cnt,R2-1);p+1到R1是在中序遍历中的右子树
L2+cnt到R2-1是在后序遍历中的右子树
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<algorithm>
#include<sstream>
using namespace std; typedef long long LL;
const int maxn=+;
int in_order[maxn],post_order[maxn],lch[maxn],rch[maxn];
int n; bool read_list(int *a){
string line;
if(!getline(cin,line)) return false;
stringstream ss (line);
n=;
int x;
while(ss>>x) a[n++]=x;
return n>;
} int build(int L1,int R1,int L2,int R2){
if(L1>R1) return ;
int root=post_order[R2];
int p=L1;
while(in_order[p]!=root) p++;
int cnt=p-L1;//左子树的结点个数
lch[root]=build(L1,p-,L2,L2+cnt-);
rch[root]=build(p+,R1,L2+cnt,R2-);
return root;
} 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);//如果u有左孩子，继续深搜，直到搜到叶子结点
if(rch[u]) dfs(rch[u],sum);
} int main(){
while(read_list(in_order)){
read_list(post_order);
build(,n-,,n-);
best_sum=;
dfs(post_order[n-],);
cout<<best<<"\n";
}
return ;
}
go---go---