当我们有一个
先序遍历序列:1,3,7,9,5,11
中序遍历序列:9,7,3,1,5,11
我们可以很轻松的用笔写出对应的二叉树。但是用代码又该如何实现?
下面我们来简单谈谈基本思想。
首先,先序遍历的顺序是根据 根-左孩子-右孩子 的顺序遍历的,那么我们可以率先确认的是先序遍历序列的第一个数就是根节点,然后中序遍历是根据 左孩子-根-右孩子 的顺序遍历的。我们通过先序遍历确认了根节点,那么我们只需要在中序遍历中找到根节点的位置,然后就可以很好地区分出,那些属于左子树的节点,那些是属于右子树的