【依据先序后序生成二叉树】
题目：已知二叉树的先序遍历序列和后序遍历序列，试编写生成该二叉树的算法。
思路：先序 pre = DLR，后序 post = LRD，D表示根结点，L表示左子树，R为右子树。
从先序出发：取先序的第一个元素pre[0]做根，第二个元素pre[1]做左子树的根（不确定也可能是右子树的根，但是先序是根左右，先认为它是左子树的根)，然后去后序序列找pre[1]这个元素的下标位置i，在后序序列里，下标i到一个元素间没有元素，说明这个树只有一个子树（可以是左子树或右子树）；有元素，那这段序列是右子树，下标i往前到post[0]是左子树。对左子树和右子树分别再这样分出根、左子树和右子树。
算法：
def func(pre[],post[]) {
int index = 0;
if(length(pre) == 0) return NULL;
node = BinTnode(pre[0]);
if(length(pre) == 1) return node;
while (pre[1] != post[index]){
index=index+1;
}
node->left = func(pre[1:index+1],post[0:index]);
node->right = func(pre[index+2:n],post[index+1:n-1]);
return node;
}
思考：或者从后序出发：取后序一个元素做根，倒数第二个元素是右子树的根A，去先序序列里找这个A的下标，这个下标往后的先序序列是右子树，往前到pre[1]是左子树，其他思路同上。
【二叉树遍历序列的应用】
相信很多备战计算机考研考生在做树和二叉树这章题的过程中，应该会遇到过以下类型的题
设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC，要求：画出这棵二叉树。
这种类型的题通常会给我们二叉树的两个遍历序列，一般是先序遍历序列和中序遍历序列，或者是后序遍历序列和中序遍历序列。可能很多同学遇到这种题会比较懵，直接选择通过各种试探来构造这棵二叉树。然后，做这种题是有规律可循的，今天就跟随心专注考研计算机老师一起来讨论这类题的解题思路。
首先，我们知道，先序遍历序列是根左右的形式即DLR形式，对于上面的例题而言，先序序列中的第一个结点A就是根结点；中序遍历序列是左根右的形式即LDR形式，所以当我们由先序序列确定出A是根结点之后，A把中序序列分成两个子序列，A左面的序列就是根结点A左子树上的结点集合，A右面的序列就是根结点A右子树上的结点集合，对于左右两子树的集合，我们又可以通过先序序列中先出现的结点确定哪个结点是子树的根，比如左子树结点集合为B，F，D组成，而在先序序列中B先于D和F出现，说明B是根A的左子树的根，C是根A的右子树的根，以此类推，得到由先序序列：ABDFCEGH以及中序序列：BFDAGEHC确定的一棵二叉树，如下图所示。简言之，由先序序列确定哪些结点是根或子树的根，由中序序列确定哪些结点是左子树结点集合以及右子树结点集合。同理，由后序序列和中序序列也可确定一棵二叉树。
