PTA L2-006 树的遍历

给出了一个二叉树的后续遍历和中序遍历，求它的层序遍历。

先弄清楚步骤：

1.由后序遍历和中序遍历来还原二叉树；

2.借助栈来实现bfs，从而实现层序遍历：

这道题的的关键在于如何还原二叉树，

大体的思路是：1.先由后序遍历来确定根节点，再从中序遍历里找到该根节点位置，

2.由中序遍历的位置来确定左子树的元素的个数，这样右子树的个数也可计算出来。

3.将左子树和右子树调用还原的函数，最后得出原二叉树。

4.借助栈来实现bfs，完成层序遍历。

#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
    int data;
    Node* left;
    Node* right;
}*BinTree;
int h[31],z[31];
queue<BinTree> q;
int flag =0;//标记是否输出过.

int find(int x){
    int l=0;
    while(z[l] != x){
        l++;
    }
    return l;
}

//zl,zr表示先序遍历数组的左右
//hl,hr表示后序遍历的数组左右
BinTree solve(int zl,int zr,int hl,int hr){
    if(zl>zr) return nullptr;
    BinTree nbt = new Node;
    nbt ->data = h[hr];
    int pos = find(nbt->data);
    int lnum = pos - zl;//左子树的元素的个数
    nbt->left = solve(zl,pos-1,hl,hl+lnum-1);
    nbt->right = solve(pos+1,zr,hl+lnum,hr-1);
    return nbt;
}
void bfs(){
    while(!q.empty()){
        BinTree t = q.front();
        q.pop();
        if(flag ==0){
            flag =1;
        }else{
            cout<<" ";
        }
        cout<<t->data;
        if(t->left) q.push(t->left);
        if(t->right) q.push(t->right);
    }
    
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;

    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    for(int i=0;i<n;i++){
        cin>>z[i];
    }
    BinTree bt = solve(0,n-1,0,n-1);
    q.push(bt);
    bfs();
}