【二叉树】玩转二叉树

左手的ㄟ右手 2024-03-23 15:03 77阅读 0赞

[题目详情 - L2-011 玩转二叉树 (pintia.cn)][- L2-011 _ _pintia.cn]

题意：

![dd74fbe51484428a93a3dae5bdb23950.png][]

思路：

给定中序序列和前序序列，求层序序列

那么肯定是要去建图

对于这棵二叉树，存树方式一定是由tree\[\]来存，下标是树的结点编号，值为权值大小

那么怎么去存树呢

这种一般都是去中序序列里找根，找到之后遍历左右子树

如果给出的是先序序列，那么就是在两个dfs之前存结点，后序的话就是在两个dfs之后存结点

存完tree数组，就相当于是建好了树

然后去BFS得到遍历序列

每次都往q里面push2\*u和2\*u+1，并记录遍历的结点，最后输出即可

Code：

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

[- L2-011 _ _pintia.cn]: https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805065406070784
[dd74fbe51484428a93a3dae5bdb23950.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/10fd58acfdce4e05a5eec3268c516ed2.png