刷题笔记——前序、中序、后序遍历知二求一

前序、中序、后序遍历知二求一是二叉树中的必考点。为了能够发现规律，不用每次都费劲地推算，特整理如下：

首先回顾一下三种遍历的特点：

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根

题型一：已知前序、中序遍历，求后序遍历

例：

【分析】：
前序：HGEDBFCA
中序：EGBDHFAC

1. 根据前序序列的特点（根左右），可知H是整个树的根。
   （至此作为选择题而言，已经可以选出正确答案B了。但我们的目标是求出后序序列）
   
2. 根据中序序列的特点（左根右），可知，EGBD位于树的左子树，FAC位于树的右子树。
   

3. 又因为前序序列的特点可知树根后面紧接着的应当是左子树的树根。所以G是左子树的树根。
   

4. 由F是右子树在前序序列中出现的第一个，根据前序序列的特点（根左右），可知F是右子树的树根。

5. 再对G重复2~4步：
   5->2 G作为根时，中序序列G的左边是它的左子树，可知只有E一个节点。G右边到H之前的都是G的右子树。可知有B、D。
   5->3 E作为G的叶子节点，无需判断左子树树根。
   5->4 由D是G的右子树在前序序列中出现的第一个，根据前序序列的特点（根左右），可知D是G的右子树的树根。

6. 由于中序序列中，B先于D出现，且D是根，所以B为D的左子树节点。

7. 对F重复2~4步，得到最终结果：
   
   后序序列为:EBDGACFH

总结（划重点！！！）：

• 前序的第一个是整个树的根
• 后序的最后一个是整个树的根
• 中序用来判别左右子树的划分
• 前序序列中左子树部分的第一个节点是左子树的根节点
• 前序序列中右子树部分的第一个节点是右子树的根节点