Tree 

 

 

题意就是多次读入两个序列，第一个是中序遍历的，第二个是后序遍历的。还原二叉树，然后从根节点走到叶子节点，找路径权值和最小的，如果有相同权值的就找叶子节点权值最小的。

最后输出来叶子节点。

 

一开始写的时候是用gets读入的，报CE，

要用fgets写，关于fgets()，传送门:

 

一开始用bfs过的，后来发现，好多人都是dfs过的，又写了一下dfs。。。

代码:

1 //二叉树的中序和后序遍历还原树并输出最短路径的叶子节点值  2 #include
     
        3 using namespace std;  4 typedef long long ll;  5 const int maxn=1e5+10;  6 const int inf=0x3f3f3f3f;  7   8 struct node{  9     int l,r,val,father; 10 }tree[maxn]; 11  12 int n=0,minn,leaf; 13 int mid[maxn],beh[maxn]; 14  15 int build(int la,int ra,int lb,int rb) 16 { 17     if(la>ra) return 0; 18     int rt=beh[rb]; 19     int p1=la; 20     while(mid[p1]!=rt) p1++; 21     int p2=p1-la; 22     tree[rt].l=build(la,p1-1,lb,lb+p2-1); 23     tree[rt].r=build(p1+1,ra,lb+p2,rb-1); 24     return rt; 25 } 26  27 /* 28 int fa[maxn]; 29  30 void bfs(int x) 31 { 32     queue
      
        q; 33     vector
       
         vec; 34     q.push(x); 35     fa[x]=0;tree[0].val=0; 36     while(!q.empty()){ 37         int rt=q.front();q.pop(); 38         if(rt==0){ 39             break; 40         } 41         tree[rt].val=tree[fa[rt]].val+rt; 42 //        cout<
        
         <