团体程序设计天梯赛-练习集 L2-011 玩转二叉树 (25分) 先序中序建树思路详解

不念不忘少年蓝@ 2023-10-11 15:03 8阅读 0赞

### L2-011 玩转二叉树 (25分) ###

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

**输入格式：**  
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

**输出格式：**  
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

**输入样例：**

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

**输出样例：**

4 6 1 7 5 3 2

> 本题采用递归建树的思想，利用中序遍历，和先序遍历的特殊性找到根节点，化大问题为一个个子问题进行解答。  
> 中序遍历：左中右。  
> 先序遍历：中左右。  
> 因而根节点为当前先序遍历范围内的最左边的节点，利用此节点，即可确立左子树与右子树的节点范围。  
> 具体步骤如下：

**int build(lmid, rmid, lpre, rpre)\{ //中序遍历的左边界与右边界，先序遍历的左边界与右边界**  
由先序遍历确定根节点为4。然后循环遍历中序节点值数组确定根节点，fa=4（注：fa初始值为lmid，每次循环+1）。左子树共有len (注：fa-lmid)个节点。  
中序遍历是：左中右。即可确定二叉树的左子树的节点值为1、2、3，右子树的节点值为5、6、7。

> 其左子树对应的参数：lmid = lmid, rmid = fa-1。右子树对应的参数: lmid =lpre+1, rmid = lpre+len。

先序遍历是：中左右。因而二叉树的左子树共有 len 个节点，

> 其左子树对应参数：lpre = lpre+1, rpre = lpre+len。右子树对应的参数：lpre=pre+len+1, rpre=rpre;

> 构建左子树：build(lmid, fa-1, lpre+1, lpre+len);  
> 构建右子树：build(fa+1, rmid, lpre+len+1, rpre);  
> 递归出口：lmid>rmid or lpre>rpre

![在这里插入图片描述][20201124100733444.png_pic_left]

需要注意的是本题需要镜像操作，因此在构建左右子树的时候需要反转一下，左子树的构建函数给右子树，右子树的构建函数给左子树。

f\[root\].rson = build(lmid, fa-1, lpre+1, lpre+len);  
f\[root\].lson = build(fa+1, rmid, lpre+len+1, rpre);

#include<bits/stdc++.h>
    #define Inf 0x3f3f3f
    const int N = 35;
    using namespace std;
    
    struct node{
        
    	int lson, rson;
    }f[35];
    int n;
    int mid[35], pre[35];
    
    
    int build(int lmid, int rmid, int lpre, int rpre){
        //中序遍历的左边界与右边界，先序遍历的左边界与右边界
    	if(lmid>rmid || lpre>rpre)
    		return 0;
    	
    	int root = pre[lpre];
    	int fa = lmid;
    	while(mid[fa]!=root) fa++;
    	int len = fa-lmid;
    	
    	f[root].rson = build(lmid, fa-1, lpre+1, lpre+len);
    	f[root].lson = build(fa+1, rmid, lpre+len+1, rpre);
    	return root;
    }
    void bfs(int root){
        
    	vector<int> ve;
    	queue<int> qu;
    
    	qu.push(root);
    	while(!qu.empty()){
        
    		int w = qu.front();
    		qu.pop();
    		if(w==0){
        
    			break;
    		}
    		ve.push_back(w);
    		if(f[w].lson){
        
    			qu.push(f[w].lson);
    		}
    		if(f[w].rson){
        
    			qu.push(f[w].rson);
    		}
    	}
    	for(int i = 0; i < n; i ++){
        
    		printf("%d%c", ve[i], i==n-1?'\n':' ');
    	}
    }
    
    int main(){
        
    	cin >> n;
    	for(int i = 0; i < n; i ++) cin >> mid[i];
    	for(int i = 0; i < n; i ++) cin >> pre[i];
    	
    	int root = build(0, n-1, 0, n-1);
    	bfs(root);
    	
    	return 0;
    }

[20201124100733444.png_pic_left]: https://img-blog.csdnimg.cn/20201124100733444.png?#pic_left