【二叉树】L2-006 树的遍历

青旅半醒 2024-03-27 08:58 16阅读 0赞

[题目详情 - L2-006 树的遍历 (pintia.cn)][- L2-006 _ _pintia.cn]

![609ef82f68d816da6913d1b15593bd1c.png][]

二叉树典中典之给定序列建树

二叉树的建树一般用结构体存而不是用链式前向星

利用二叉树的性质边递归边建树

这里的dfs是利用序列递归找根，顺便建树

先把后序序列翻转成前序序列，然后就能递归建树了

感觉有点抽象

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=30+10,mxe=30+10;
    struct ty{
        int l,r;
    }tree[mxe<<1];
    vector<int> v;
    queue<int> q;
    int n,idx=0;
    int a[mxn],b[mxn];
    int dfs(int l,int r){
        //cout<<l<<" "<<r<<'\n';
        if(l>r) return 0;
        int rt=++idx;
        int ansi;
        for(int i=l;i<=r;i++){
            if(b[i]==a[idx]){
                ansi=i;
                break;
            }
        }
        tree[rt].r=dfs(ansi+1,r);
        tree[rt].l=dfs(l,ansi-1);
        return rt;
    }
    void bfs(int rt){
        q.push(rt);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            if(u==0) continue;
            v.push_back(u);
            q.push(tree[u].l);
            q.push(tree[u].r);
        }
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n;
        for(int i=n;i>=1;i--) cin>>a[i];//后
        for(int i=1;i<=n;i++) cin>>b[i];//中
        int rt=dfs(1,n);
        bfs(rt);
        for(int i=0;i<v.size();i++) cout<<a[v[i]]<<" \n"[i==v.size()-1];
    }

附上二叉树的一般写法：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    queue<int> q;
    
    int n,len=0;
    int tree[mxn];
    int hx[mxn],zx[mxn],ans[mxn];
    
    void dfs(int rt,int l1,int r1,int l2,int r2){
        if(l1>r1||l2>r2) return;
        if(l1==r1){
            tree[rt]=hx[l1];
            return;
        }
        for(int i=l2;i<=r2;i++){
            if(zx[i]==hx[r1]){
                dfs(rt<<1,l1,i-l2+l1-1,l2,i-1);
                dfs(rt<<1|1,i-l2+l1,r1-1,i+1,r2);
                tree[rt]=hx[r1];
            }
        }
        return;
    }
    void bfs(int x){
        q.push(x);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            if(tree[u]!=0){
                ans[++len]=tree[u];
                q.push(u<<1);
                q.push(u<<1|1);
            }
        }
    }
    signed main(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>hx[i];
        for(int i=1;i<=n;i++) cin>>zx[i];
        dfs(1,1,n,1,n);
        bfs(1);
        for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
    }

[- L2-006 _ _pintia.cn]: https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805069361299456
[609ef82f68d816da6913d1b15593bd1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/13e06d059b0241a093775ffd00aaf642.png