本节主要介绍如何根据二叉树的遍历序列还原二叉树
1.根据前序遍历序列ABCDEF和中序遍历序列CBAEDF如何判断还原二叉树
（1）根节点：
首先根据前序序列的第一个字母A确定根节点；
（2）确定左右子树的序列元素：
根据中序序列确定左子树的序列是C、B，右子树的序列是E、D、F
（3）确定左子树：
根据前序序列ABC顺序判断B是A的左子树的根节点，但是不能判断C是B的左子节点还是右子节点；
根据中序序列CBA顺序确定C是B的左子节点
（4）确定右子树：
根据前序序列DEF顺序确定D是A的右子树的根节点，E是D的子节点，但不知道是左子节点还是右子节点，也不清楚F是D的子节点还是孙子节点；
根据中序序列EDF顺序确定E是D的左子节点，F是D的右子节点
综上即确定了二叉树，然后我们可以确定后序遍历序列是CBEFDA
2.根据中序遍历序列ABCDEFG和后序遍历序列BDCAFGE还原二叉树
（1）确定根节点：
根据后序序列的最后一个元素是E确定E是根节点
（2）确定左右子树的序列元素
根据中序序列以E为分割点确定左子树序列是ABCD，右子树序列是FG
（3）确定左子树
根据后序序列BDCA确定最后一个元素A是左子树的根节点，C是A的子节点，但不能确定是左节点还是右节点，BD是C的子孙，但不能确定都是儿子或有一个是孙子；
根据中序序列ABCD确定BCD是A的右子树，即C是A的右子节点；且B是C的左子节点，D是C的右子节点
（4）确定右子树
根据后序序列FGE确定G是E的右子树的根节点，F是G的子节点，但不知道是左子节点还是右子节点；
根据中序序列EFG确定F是左子节点
综上即确定了二叉树，得到前序序列是EACBDGF
3.总结
（1）综合上面的两种情况：可以把还原二叉树的过程看做四个步骤：
确定根节点：根据前（后）序序列的第一位（最后一位）确定根节点；
确定左右子树元素：根据中序序列确定左右子树的元素；
确定左子树：先根据前（后）序序列确定左子树的根节点及其子节点，然后根据中序序列确定左子树的剩余元素的位置；
确定右子树：先根据前（后）序序列确定右子树的根节点及其子节点，然后根据中序序列确定右子树的剩余元素的位置
（2）二叉树遍历的性质：
已知前序遍历序列和中序遍历序列可以唯一确定一棵二叉树；
已知后序遍历序列和中序遍历序列可以唯一确定一棵二叉树；
已知前序序列和后序序列是不能确定一棵二叉树的，因为只能确定根节点，而无法确定其余元素的位置
