考研题
image.png
要点
- 二叉树的前序、中序、后序遍历，一定要完全熟透，因为最后题做的对不对完全靠这个
- 根据前序和中序还原二叉树，固定模式M1（https://www.51cto.com/article/678237.html）
- 根据中序和后序还原二叉树，固定模式M2（https://www.51cto.com/article/678237.html）
- 特性
- 后序的最后一个元素为根结点
- 前序的第一个元素为根结点
解题思路
- 从后序序列可以看到A是根结点
- 中序序列可以看出来CBFxx是A的左子树，JKIGx为A的右子树（tips：一般情况都这么出题了可以假定先序序列就是ABCDEFGHIKJK，可以加速解题，当然也不一定）
- 先序序列是A_CDE_GHI_K，从中序的CB__FA基本上可以判断先序是ABCDEFGHIJK
- J肯定是GHI和K之间
- 中序中可以看到F是A最右的子节点，那么在先序的序列也是最后的元素
- 这时候只要知道中序基本上就能还原二叉树了，套用固定模式M1
4.中序的CB__FA中DE的顺序在先序和后序中分别是DE和ED，那么在中序中一定是DE，这时候中序的序列也出来了那就是CBDEFAHJKIG，根据先序和中序就可以确定二叉树的结构了
tips
- 实际做题的时候可以快速的假设先序就是ABCDEFGHIJK，然后小心的求证，这样题做起来最快
- 几个要点一定滚瓜烂熟
