Question

根据先序和中序序列生成二叉树

Answer 1

在二叉树中，有三种主要的遍历方式（假设父节点为N，左孩子为L，右孩子为R）：

先序遍历：N -> L -> R

中序遍历：L -> N -> R

后序遍历：L -> R -> N

假设现有一颗二叉树如上图所示，上述二叉树的先序遍历和中序遍历结果为：

先序遍历：ABCDEF

中序遍历：CBDAEF

分析： 先序遍历服从规则“根左右”，所以，对于一个先序遍历得到的数组，第一个元素一定是根节点；中序遍历服从规则”左根右“，所以由此可知，对于一个中序遍历得到的数组，根节点左边的元素都属于根节点的左子树，而根节点右边的元素都属于根节点的右子树。所以，可以先通过先序遍历的第一个元素确定根节点，然后通过中序遍历结合根节点，获得当前根节点的左右子树，再将子树看成一棵独立的树，继续使用先序遍历判断根节点，中序遍历判断子树的方式，最终建立起整棵树 。

详细算法如下：

1、先序或中序为空则返回，否则，通过先序序列创建根结点，再通过根节点在中序遍历的位置找出左右子树。

2、在根绝点的左子树中，找左子树的根结点（在先序中找），转步骤1。

3、在根节点的右子树中，找右子树的根结点（在先序中找），转步骤1。

根据上述算法，可以看出创建出二叉树的关键在于先序序列和中序序列的划分，在对序列进行划分的时候要注意边界的问题。

递归方式

非递归方式