题目描述

通过后序序列和中序序列构建二叉树

算法1

C++ 代码

#include<iostream>
#include<map>
#include<queue>
using namespace std;
const int N=35;
int n;
int postorder[N],midorder[N];
//存储中序序列中值对应的下标
int position[N];
map<int,int> l,r;//对应的左子树和右子树

void bfs(int root){
    queue<int> q;
    q.push(root);
    while(q.size()){
        auto t=q.front();q.pop();
        cout<<t<<" ";
        if(l.count(t)){
             q.push(l[t]);
        }
        if(r.count(t)){
             q.push(r[t]);
        }

    }
}

int build(int ml,int mr,int pl,int pr){

    //(1)在后序序列中找到root值
    int root=postorder[pr];
    //(2)在中序序列中找到root的位置
    int k=position[root];
    //(3)如果对应位置有左子树
    if(k>ml){
        l[root]=build(ml,k-1,pl,pl+k-1-ml);
    }
    //(4)如果对应位置有右子树
    if(k<mr){
        r[root]=build(k+1,mr,pl+k-ml,pr-1);
    }
    //(5)返回根节点

    return root;

}

int main(){
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>postorder[i];
    }

    for(int i=1;i<=n;i++){
        cin>>midorder[i];
        position[midorder[i]]=i;
    }

    int root=build(1,n,1,n);

    bfs(root);

    return 0;
}