#include<stdio.h> #include<iostream> #include<string> #include<sstream> #include<algorithm> using namespace std; const int maxn=10010; int inorder[maxn]; //中序遍历数组 int postorder[maxn]; //后序遍历数组 int lch[maxn]; //二叉树左子树 int rch[maxn]; //二叉树右子树 int n; int best_sum,best; //最小权值和 最小节点编号 int read_list(int *a) { string line; if(!getline(cin,line)) return 0; 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) { if(l1>r1) // return 0; int root=postorder[r2]; //根节点 int p=l1; //根节点在中序的位置 while(inorder[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; } void dfs(int v,int sum) //dfs搜索 { sum+=v; if(!lch[v]&&!rch[v]) { if(sum<bestsum||(sum==best_sum&&v<best)) { best=v; bestsum=sum; } } if(lch[v]) dfs(lch[v],sum); if(rch[v]) dfs(rch[v],sum); } int main() { while(readlist(in_order)) //读入中序 { readlist(post_order); //后序 build(0,n-1,0,n-1); //建立二叉树 bestsum=0x3f3f3f3f; dfs(postorder[n-1],0); cout<<best<<"\n"; } }