杭電1710題、天梯賽L2-011（由二叉樹的前序、中序周遊求後序周遊）

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int val;  //節點的值 
    node* l;  //左子樹 
    node* r;  //右子樹 
};
int qx[1005]; //前序周遊 
int zx[1005]; //後序周遊 
node* build(int ql,int qr,int zl,int zr)  //建樹函數 
{
    if(zl>zr)  return NULL;  //如果左邊界大于右邊界，結束 
    int root=qx[ql];  //前序周遊第一個就是根節點的值 
    int pos=zl;   //pos為根節點在中序周遊中的位置，初始化為中序周遊的左邊界 
    while(zx[pos]!=root)  pos++; //求出根節點在中序周遊中的位置 
    int len=pos-zl;  //求出左子樹的長度 
    node* rt=new node();  //申請記憶體 
    rt->val=root;   //存入根節點的值 
    rt->l=build(ql+1,ql+len-1,zl,pos-1);  //建立左子樹 
    rt->r=build(ql+len+1,qr,pos+1,zr);   //建立右子樹 
    return rt;
}
int ans;
void houxu(node* rt)  //後序周遊 
{
    if(rt==NULL)  return;  //如果節點為空，結束 
    else
    {
        houxu(rt->l);  //周遊左子樹，輸出值 
        houxu(rt->r);  //周遊右子樹，輸出值 
        if(ans==0)     //最後輸出根節點的值 
        {
            ans++;
            cout<<rt->val;
        }
        else cout<<" "<<rt->val;
    }
}
int main()
{
    int n;
    node* rt;
    while(cin>>n)  //輸入數組長度 
    {
        for(int i=0;i<n;i++)  cin>>qx[i];  //輸入前序周遊 
        for(int i=0;i<n;i++)  cin>>zx[i];  //輸入後序周遊 
        rt=build(0,n-1,0,n-1);  //建樹 
        ans=0;  //标記是否是第一個輸出的 
        houxu(rt);  //後序周遊輸出 
        cout<<endl;
    }
    return 0;
}      

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int val;  //節點的值 
    node* l;  //左子樹 
    node* r;  //右子樹 
}; 
int zx[35];  //中序周遊數組 
int qx[35];  //前序周遊數組 
node* build(int zl,int zr,int ql,int qr)  //建樹操作 
{
    if(zl>zr)  return NULL; //如果左邊界大于右邊界，結束 
    int ans=qx[ql];  //前序周遊的第一個就是根節點的值 
    int pos=zl;  //初始化父節點的位置在中序周遊的左邊界 
    while(zx[pos]!=ans)  pos++;  //找到父節點在中序周遊中的位置 
    int len=pos-zl;  //求出左子樹的長度 
    node* rt=new node();  //申請記憶體 
    rt->val=ans;  //存父節點的值 
    rt->l=build(zl,pos-1,ql+1,ql+len-1);  //建立左子樹 
    rt->r=build(pos+1,zr,ql+len+1,qr);  //建立右子樹 
    return rt;  //又是這錯了，一定要傳回根節點 
}
bool flag;
void cengci(node* rt)  //鏡像翻轉的層次周遊 
{
    int ans;
    queue<node*>q;
    while(!q.empty())  q.pop();
    if(rt!=NULL) q.push(rt);  //根節點不為空，存父節點 
    while(!q.empty())  
    { 
        rt=q.front();  //取出父節點 
        q.pop();   //将父節點從隊列中删除 
        ans=rt->val;  
        if(flag)   //輸出父節點的值 
        {
            flag=false;
            cout<<ans;
        }
        else cout<<" "<<ans; 
        if(rt->r!=NULL)  q.push(rt->r);  //将右子樹壓入隊列 
        if(rt->l!=NULL)  q.push(rt->l);  //将左子樹壓入隊列 
    }
}
int main()
{
    node* rt;
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;i++)  cin>>zx[i];  //輸入前序周遊 
        for(int i=0;i<n;i++)  cin>>qx[i];  //輸入中序周遊 
        rt=build(0,n-1,0,n-1);  //建樹 
        flag=true;
        cengci(rt);  //翻轉後的層次周遊 
        cout<<endl;
    }
    return 0;
}