题目描述

树的遍历

样例

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

4 1 6 3 5 7 2

算法1 手写hash

时间复杂度 O（n）

n个结点

参考文献 算法基础课

C++ 代码

/**为什么放着STL不用非得手写hash？ 别问 问就是闲的**/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 67;
const int null = 0x3f3f3f3f;
int postorder[maxn];
int inorder[maxn];
//hash表
int l[maxn];
int r[maxn];
int pos[maxn]; //pos[i]=j; i=f(结点的值) j=结点在中序序列中的位置
//一定要记得开一个p数组来记录映射的位置 必须有这个数组 
int p[maxn]; 
//记录pos每个结点映射到hash表（pos数组）中的下标 
//因为我们find搜索时需要按照节点存入hash表中的下标来搜索 而不是存入的值

int find(int x,int h[]) //将大数映射到小范围上
{
    int k = (x%maxn+maxn)%maxn;
    while(h[k]!=null&&h[k]!=x)
    {
        k++;
        if(k==maxn) k=0;
    }
    return k;
}

int build(int il,int ir,int pl,int pr)
{
    int root = postorder[pr];
    int k = pos[p[root]];
    if(il<k) l[ p[root] ] = build( il,k-1,pl,pl+k-1-il );
    if(ir>k) r[ p[root] ] = build( k+1,ir,pl+k-il,pr-1 );
    return root;
}


int q[maxn];
void bfs(int root)
{
    int tt=-1;
    int hh=0;
    q[++tt]=root;
    while(hh<=tt)
    {
        int t=q[hh++];
        cout<<t<<" ";
        if(l[p[t]]!=null) q[++tt]=l[p[t]];
        if(r[p[t]]!=null) q[++tt]=r[p[t]];
    }
    return ;
}


int main()
{
    memset(l,0x3f,sizeof l);
    memset(r,0x3f,sizeof r);
    memset(pos,0x3f,sizeof pos);
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>postorder[i];
    for(int i=0;i<n;i++)
    {
        cin>>inorder[i];
        //通过find函数把inorder[i]映射到一个位置上 并将该位置的值赋值为i
        p[inorder[i]] = find(inorder[i],pos); //p记录inorder[i]映射到hash表pos的位置
        pos[p[inorder[i]]]=i;
    }
    int root = build(0,n-1,0,n-1);
    bfs(root);
}