手推二叉树的思路

很多题目涉及到：已知先序，中序，后序中的两种排列，希望求出另外一种。
显然，除了先序+后序不能唯一确定一棵二叉树，另外都可以确定。
针对可以确定唯一二叉树的，给出以下做题思路。

做题思路：

先确定根结点，将所有点分为左右两堆，之后再依次确定左右两侧的二叉树。

知识储备：

特性(1)，对于前序遍历，第一个肯定是根节点；
特性(2)，对于后序遍历，最后一个肯定是根节点；
特性(3)，中序遍历可以以节点为界限，划分左右树集合元素的作用。

例如：

先序ABCDEF，中序CBAEDF，后序CBEFDA
节点按照深度排序{A}{BD}{CEF}

具体操作：

·根据先序遍历序列和中序遍历序列构建二叉树：

step1、先序遍历的第一个结点总是根结点。
step2、中序遍历中，根结点左侧的所有结点属于左子树，根结点右侧所有结点属于右子树。
step3、在先序遍历和中序遍历中按照原顺序，在两种遍历中都只留下左树，或者都只留下右树，把留下的部分视为独立的树，在留下的元素中继续step1和2即可。

·根据后序遍历序列和中序遍历序列构建二叉树：

step1、后序遍历的最后一个结点总是根结点。
step2、中序遍历中，根结点左侧的所有结点属于左子树，根结点右侧所有结点属于右子树。
step3、在后序遍历和中序遍历中按照原顺序，在两种遍历中都只留下左树，或者都只留下右树，把留下的部分视为独立的树，在留下的元素中继续step1和2即可。