数据结构-5.8.由遍历序列构造二叉树
一.不同二叉树的遍历序列：
1.中序遍历：
2.前序遍历：
3.后序遍历：
4.层序遍历：
5.结论：
由上述图片可知，给定一个二叉树，那么它的中(前/后)序遍历必定唯一，若只给出一颗二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一颗二叉树(因为结果可能有多个)：
二.例题：
1.已知前序+中序遍历序列：
核心：先根据先序遍历找到根结点，然后通过中序遍历找出左子树和右子树，再通过先序遍历和中序遍历进行同样逻辑的分析
例一：
思路：先看二叉树的中序遍历序列BDCAE，其中每一个结点都有可能是二叉树的根结点，
再分析二叉树的前序遍历序列ADBCE，在所分析的树中前序遍历的第一个结点一定是根结点，因此A是根结点，此
时就可以确定该二叉树的左子树的中序遍历序列为BDC，右子树只有一个结点E，首先可以确定左子树一共有3个结
点(长度为3)，在先序遍历中，由于该二叉树的左子树长度为3且根结点为A，那么左子树的先序遍历序列为DBC(长
度为3)，剩下的就是右子树的先序遍历序列E：
核心：先根据先序遍历找到根结点，然后找出左子树和右子树，再通过先序遍历和中序遍历进行同样逻辑的分析
相同的逻辑可知，由先序遍历(也叫前序遍历)可知左子树的根结点为D，由中序遍历可知D结点的左子结点为B，D结点的右子结点为C：下述图片D的右子结点为C，打错了
最后可以根据题目的前序遍历或者中序遍历来验证是否正确；
例二：
根据先序遍历可知根结点为D，然后根据中序遍历可知左子树的结点有EAF，右子树的结点有HCBGI：
左子树的结点有EAF，长度为3；右子树的结点有HCBGI，长度为5；
先看左子树EAF：由前序遍历可知左子树的根结点为A，中序遍历中E和F分别在A的左边和右边，所以A的左子结点为E，A
的右子结点为F：
再看右子树HCBGI：由前序遍历可知右子树的根结点为B，中序遍历中HC和GI分别在B的左边和右边：
B结点下的左子树的结点有HC，右子树的结点有GI，
先看左子树HC：由前序遍历可知根结点为C，由中序遍历可知左子结点为H，没有右子结点了；
先看右子树GI：由前序遍历可知根结点为G，由中序遍历可知没有左子结点，右子结点为I；
所以，该二叉树的形状为：
2.已知后序+中序遍历序列：
核心：先根据后序遍历找到根结点，然后通过中序遍历找出左子树和右子树，再通过后序遍历和中序遍历进行同样逻辑的分析
例一：
由后序遍历可知根结点为D(因为在所分析的树的结点中最后出现)，由中序遍历可知左子树包含结点EAF，右子树包含结点HCBGI：
先看左子树EAF：由后序遍历可知根结点为A，由中序遍历可知A结点的左子结点为E，A结点的右子结点为F，左子树如下：
再看右子树HCBGI：由后序遍历可知右子树HCBGI的根结点为B，由中序遍历可知B结点的左子树包含结点HC，右子树包含结点GI：
先看左子树HC：由后序遍历可知左子树HC的根结点为C，由中序遍历可知C结点的左子结点为H，没有右子结点；
再看右子树GI：由后序遍历可知右子树GI的根结点为G，由中序遍历可知G结点的左子结点不存在，右子结点为I；
所以，该二叉树的形状为：
3.已知层序+中序遍历序列：
例一：
在所分析的树中，由层序遍历可知根结点为D，由中序遍历可知左子树包含结点EAF，右子树包含结点HCBGI：
左子树和右子树各只有一个根结点，因此由前序遍历可知左子树的根结点为A，右子树的根结点为B，由中序遍历可知左子树EAF中结点A的左子结点为E，A的右子结点为F，右子树HCBGI中结点B的左子树包含结点HC，B的右子树包含结点GI：
此时在第三层，由层序遍历可知首先出现的是E和F，之后出现的是C和G，
再根据中序遍历序列可知C结点的左子结点为H，没有右子结点，G结点没有左子结点，右子结点为I，
所以，该二叉树的形状为：
例二：
在所分析的树中，由层序遍历可知根结点为A，由中序遍历可知左子树不包含结点，右子树包含结点CBED：
可知第二次只有右子树，A后面紧跟的就只能是右子树的根结点B，由中序遍历序列可知结点B的左子结点为C，右子树为ED：
此时该访问第三层，由层序遍历序列可知先访问结点C，再访问结点D，所以B结点的右子结点为D，由中序遍历序列可知结点D的左子结点为E，不存在右子结点，
所以，该二叉树的形状为：
例二中层序遍历的序列中根结点后面跟的并不是左子树的根结点，因为从中序遍历序列可知该二叉树的左子树为空，只有右子树。
三.总结：
根结点为A，它的左子结点为B，没有右子结点，
根结点为A，没有左子结点，它的右子结点为B，
显然这是两棵不同的二叉树，但他们的前/后/层序遍历序列都一样，因此前序，后序，层序遍历序列的两两组合无法唯一确定一棵二叉树，要想唯一确定一棵二叉树，必须要与中序遍历序列组合。