【数据结构】由遍历序列构造二叉树

若只给出一棵二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一棵二叉树。所以，需要通过组合来实现由遍历序列构造二叉树。

1. 前序+中序遍历序列

示例

解析：根据前序遍历规则，根结点首先被访问，所以A是树的根结点。而在中序遍历中，根结点之前的是在左子树，那么BDC肯定是左子树的部分；根结点之后的是在右子树，那么E肯定是右子树的部分。然后对BDC做同样的分析，得到最终唯一的二叉树。

2. 后序+中序遍历

示例

解析：根据后序遍历规则，根结点最后被访问，所以D是树的根结点。而在中序遍历中，根结点之前的是在左子树，那么EFA肯定是左子树的部分；根结点之后的是在右子树，那么HCBGI肯定是右子树的部分。然后对EFA和HCBGI做相同的分析，得到唯一的二叉树。

3. 层序+中序遍历

示例

解析：根据层序遍历规则，根结点最先被访问，那么D是树的根结点。而在中序遍历中，根结点之前的是在左子树，那么EFA肯定是左子树的部分；根结点之后的是在右子树，那么HCBGI肯定是右子树的部分。然后对EFA和HCBGI做相同的分析，得到唯一的二叉树。

4. 小结

关键点：

1. 找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点。
2. 前序、后序、层序序列的两两组合无法唯一确定一棵二叉树。