Question

根据二叉树的其中两个序列，画二叉树？请教高手指点技巧。。

虽然知道二叉树的各种遍历方法，但在已知两种序列，画出二叉树为什么还是那么难呢？有什么规律可循呢？

Answer 1

已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：
1. 根据前序序列的第一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在前序序列中确定左右子树的前序序列；
4. 由左子树的前序序列和中序序列建立左子树；
5. 由右子树的前序序列和中序序列建立右子树。
已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。
例如：已知二叉树的中序序列BDCEAFHG , 后序序列DECBHGFA。
先序：EBADCFHGIKJ->根：E
根据根结点来划分中序序列
中序：ABCDEFGHIJK->ABCD+E+FGHIJK
由左右子树的结点集合来划分先序序列->先序：E+BADC+FHGIKJ
分别对左右子树运用相同的方法分解出根和其左右子树的结点集合。依次递归