内容简介：前面分享了《每种遍历输出的就是一个序列。如果只给我们一个序列，我们是没办法反唯一的向构造出一个二叉树的。比如前序序列
一、背景
前面分享了《 二叉树就是这么简单 》，里面提到二叉树有三种遍历方式：前序遍历、中序遍历、后序遍历。
每种遍历输出的就是一个序列。如果只给我们一个序列，我们是没办法反唯一的向构造出一个二叉树的。
比如前序序列 [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-
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
数据结构与算法分析
Frank.M.Carrano / 金名 / 清华大学出版社 / 2007-11 / 98.00元
“数据结构”是计算机专业的基础与核心课程之一，Java是现今一种热门的语言。本书在编写过程中特别考虑到了面向对象程序设计（OOP）的思想与Java语言的特性。它不是从基于另一种程序设计语言的数据结构教材简单地“改编”而来的，因此在数据结构的实现上更加“地道”地运用了Java语言，并且自始至终强调以面向对象的方式来思考、分析和解决问题。 本书是为数据结构入门课程（通常课号是CS-2）而编写的教......一起来看看 《数据结构与算法分析》 这本书的介绍吧!
