【数据结构】树的遍历

【数据结构】树的遍历

​​题目链接​​

思路

如果树节点都不一样，那么我们可用通过树的中序遍历和后序遍历确定一棵树。
我们通过哈希表来存左儿子和右儿子`

l[root]=
r[root]=

构造树
我们通过后序遍历得到最后一个点是根节点，然后在中序遍历中找到root,同时得到左子树和右子树在中序遍历中的区间。由于是同一棵树，中序遍历子树区间长度和后序遍历的是相同的，我们可用中序遍历得到的区间长度推算出后序遍历中左右子树区间位置
不过要先看一下子树是否存在

层序遍历
这个比较简单从root开始BFS，如果子树存在那就加入队列

代码

#include<bits/stdc++.h>
using namespace std;

const int N=40;
int n;
int postorder[N],inorder[N];
unordered_map<int,int>l,r,pos;

int build (int il,int ir,int pl,int pr)//il,ir中序遍历左右区间，pl,pr后序遍历左右区间
{
    int root = postorder[pr];
    int k=pos[root];//root在中序遍历中位置
    if(il<k)l[root]=build(il,k-1,pl,pl+k-1-il);
    if(ir>k)r[root]=build(k+1,ir,pr-ir+k,pr-1);//注意,后续遍历右边界是pr-1,不是pr
    return root;
}

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 main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>postorder[i];
    for(int i=0;i<n;i++)
    {
        cin>>inorder[i];
        pos[inorder[i]]=i;
    }
    int root=build(0,n-1,0,n-1);
    bfs(root);
}