已知中序遍历和层序遍历重构树

忘是亡心i 2023-02-11 08:51 94阅读 0赞

#### 问题描述： ####

已知一棵树的层序遍历结果是1 2 3 4 5 6 7；  
中序遍历结果是6 4 2 5 7 1 3，那么如何重构这颗树呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]

#### 求解思路： ####

层序遍历和前中后遍历不同的一点在于左右子树的结点是混合出现的  
因此在递归建树的过程中关键的一点就是将左右子树分割出来

#### 算法设计 ####

首先需要知道层次排序第一个出现的是根结点  
![在这里插入图片描述][20200522163145948.png]  
然后在中序序列中找根结点的位置，记录到k中，那么其左边的结点属于左子树，右边的结点属于右子树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 1]  
接下来遍历levelorder数组，对于每个数字，判断其是否在左子树中，即（是否在inorder【inl，k-1】区间内能找到）。如果找到则放入levelleft，否则放入levelright，然后分别递归左右子树

**注意**  
因为对于判断层序遍历中的每个点是属于左子树还是右子树都需要一一遍历，因此在极端情况下，例如所有结点都在左子树时运算复杂度是很高的

#### 代码 ####

#include<iostream>
    #include<vector>
    using namespace std;
    struct node{ 
    	int data;
    	node *l,*r;
    };
    vector<int> inorder; 
    node* create(vector<int> level,int il,int ir)
    { 
    	if(il>ir)return NULL;
    	node* root=new node; 
    	root->data=level[0];
    	int k;
    	for(k=il;k<=ir;k++)//找根结点位置
    	{ 
    		if(inorder[k]==level[0])break;
    	}
    	vector<int> levelleft,levelright;
    	for(int i=1;i<level.size();i++)
    	{ 
    		bool flag=false;//判断是否在左子树中找到
    		for(int j=il;j<k;j++)
    		{ 
    			if(inorder[j]==level[i])
    			{ 
    				flag=true;
    				break;
    			}
    		}
    		if(flag)levelleft.push_back(level[i]);//找到放入左子树
    		else levelright.push_back(level[i]);//放入右子树
    	} 
    	root->l=create(levelleft,il,k-1);
    	root->r=create(levelright,k+1,ir);
    	return root;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200522162133225.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70
[20200522163145948.png]: https://img-blog.csdnimg.cn/20200522163145948.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200522164628940.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70