动态二叉树层序遍历用bfs

#include<bits/stdc++.h>
using namespace std;
int const N=30+7;
int n;
int z[N],q[N];
struct node{
    int w;
    node *l,*r;
};
node* dfs(int l1,int r1,int l2,int r2){
    if(l1>r1||l2>r2) return NULL;
    node* rt=new node;   //注意 
    rt->w =q[l2];
    int i=l1;
    for(i=l1;i<=r1;++i){
        if(z[i]==q[l2]) break;
    }
    rt->r =dfs(l1,i-1,l2+1,l2+i-l1);
    rt->l =dfs(i+1,r1,l2+i-l1+1,r2);
    return rt;
}
void bfs(node* rt){
    queue<node*>q;
    q.push(rt);
    while(!q.empty()){
        node *now=q.front();
        if(now->l!=NULL) q.push(now->l );
        if(now->r!=NULL) q.push(now->r );
        q.pop();
        cout << now->w ;
        if(!q.empty()) cout << " ";
    }
}
int main(){
    cin >> n;
    for(int i=1;i<=n;++i) cin >> z[i];
    for(int i=1;i<=n;++i) cin >> q[i];
    node *rt;
    rt=dfs(1,n,1,n);
    bfs(rt);
    return 0;
}
全部评论

相关推荐

10-10 01:10
已编辑
深圳大学 测试开发
面了100年面试不知...:六月到九月,四个项目一个实习,是魔丸吗
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务