(模板)已知二叉树先序(后序)中序,求这棵二叉树

柔情只为你懂 2022-04-23 01:04 169阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70][]

这种题型为考研常考题型。看这张图就比较好理解了,先序的第一个元素或后序的最后一个元素为当前子树的根

确认先序/后序的根后,我们遍历中序序列寻找根在中序序列中的位置,上图中为ink,那么ink左边的序列位于二叉树的左子树部分,

ink右边的序列位于二叉树的右子树部分

我们确认左子树部分k个元素,就可以确定子树区间了

## 先序左子树区间 \[POSTL+1,POSTL+k\] ##

## 先序右子树区间 \[POSTL+k+1,POSTR\] ##

## 中序左子树区间 \[inkL, k-1\] ##

## 中序右子树区间 \[k+1 inkR\] ##

## 后序左子树区间 \[POSTL,POSTL+k-1\] ##

## 后序右子树区间 \[POSTL+k,POSTR-1\] ##

下面给出模板

类似的习题见:[https://blog.csdn.net/alex1997222/article/details/86600218][https_blog.csdn.net_alex1997222_article_details_86600218]

Node* CreateTree(int postL, int postR, int inL, int inR) {
    	if (postL > postR) return nullptr;
    	int curPostRoot = postArrays[postR];
        //确定根的值
    	Node* root = new Node(curPostRoot);
    	int curInRoot = -1;
    	int k;
        //在中序中查找根,确定根的位置
    	for (k = inL; k <= inR; ++k) {
    		if (inArrays[k] == curPostRoot) {
    			curInRoot = inArrays[k];
    			break;
    		}
    	}
    	if (curInRoot == -1) return nullptr;
        //后序遍历
    	int numleft = k - inL;  
    	root->lchild = CreateTree(postL,postL+numleft-1,inL,k-1);
    	root->rchild = CreateTree(postL+numleft,postR-1,k+1,inR);
        //先序遍历
        int numleft = k - inL;  
    	root->lchild = CreateTree(postL+1,postL+numleft,inL,k-1);
    	root->rchild = CreateTree(postL+numleft+1,postR,k+1,inR);
    
    	return root;
    }

##  ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70]: /images/20220323/7d20df53403e4240b5f0080c1c53b5ed.png
[https_blog.csdn.net_alex1997222_article_details_86600218]: https://blog.csdn.net/alex1997222/article/details/86600218