前序、中序、后续构造二叉树?

作者: | 更新日期:

二叉树是一个很基础的数据结构,这里面有不少学问。

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/HEsqxzUcAiLlJ4DLMCPsyQ

一、背景

前面分享了《二叉树就是这么简单》,里面提到二叉树有三种遍历方式:前序遍历、中序遍历、后序遍历。

每种遍历输出的就是一个序列。如果只给我们一个序列,我们是没办法反唯一的向构造出一个二叉树的。
比如前序序列[3,9,20,15,7],我们可以确定3是根,但是之后的就不知道哪个属于左子树,哪个属于右子树。

但是给我们一个中序序列和后序序列,我们就可以唯一的构造出一个二叉树了。

二、中序与后序

假设中序和后序的数据如下:

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

这里假设我们实现了一个函数,传入两个中序序列和后序序列,我们可以返回对应的二叉树。

第一步:根据后序序列最后一个位置,我们可以确定根是postorder[4]=3
然后在中序序列中,查找到根的位置是inorder[1]=3

第二步:根据中序序列根的位置,我们可以得到左子树的中序序列[9]和右子树的中序序列[15,20,7]
接着,我们也可以根据两个子树的序列长度,得到左子树的后序序列[9]和右子树的后序序列15,7,20

第三步:递归函数自身,分别得到左子树和右子树。

注意事项:这里有个特殊处理:如果序列为空,则返回空二叉树。

三、最后

对于中序和前序,其实是类似的方法,作为思考题留给大家吧。
另外再附加一道思考题:前序和后序能得到二叉树吗?为什么?

-EOF-

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/HEsqxzUcAiLlJ4DLMCPsyQ

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越