适用：考研408数据结构
章节：第5章 树与二叉树
重点题型：

1. 已知两种遍历，求第三种遍历

2. 判断一棵二叉树能否唯一确定

3. 已知前序和后序，判断中序可能/不可能

4. 判断“前序与后序互逆”时二叉树的结构性质

一、先把三种遍历顺序记死

前序：根 -> 左 -> 右 中序：左 -> 根 -> 右 后序：左 -> 右 -> 根

最重要的两个定位：

前序第一个结点 = 根 后序最后一个结点 = 根

而中序的作用是：

用根结点把序列切成左子树和右子树

所以这类题最核心的一句话是：

前序/后序负责找根，中序负责切左右。

二、哪两种遍历能唯一确定二叉树

这是408非常常见的概念题。

原因很简单。

如果有中序，一旦知道根，就能立刻知道：

根左边 = 左子树 根右边 = 右子树

但只有前序和后序时，如果某个结点只有一个孩子，就无法判断这个孩子究竟是：

左孩子 还是 右孩子

所以：

有中序，基本能还原； 没中序，一般不唯一。

三、题型1：已知前序 + 中序，求后序

例如：

中序：ABCD 前序：CABD

要求后序。

解题过程

前序第一个结点一定是根，所以根为：

C

在中序序列中找到 C：

AB | C | D

因此：

左子树：AB 右子树：D

左子树有2个结点，所以从前序去掉根 C 后：

左子树前序：AB 右子树前序：D

继续看左子树：

前序：AB 中序：AB

前序第一个 A 是根。

在中序中：

A | B

说明 A 没有左孩子，B 是 A 的右孩子。

整棵树为：

C / \ A D \ B

按照后序：

左 -> 右 -> 根

左子树后序：

BA

右子树：

D

最后访问根 C：

BADC

所以：

后序 = BADC

四、已知前序 + 中序的固定模板

以后不需要重新想，直接按这个流程：

1. 前序第一个元素找根 2. 在中序中找到根 3. 中序按根切成： 左子树 | 根 | 右子树 4. 根据左右子树结点数量 去切前序序列 5. 对左右子树重复上述过程 6. 最后按题目要求写出后序

五、题型2：已知后序 + 中序，求前序

方法完全类似，只改一个地方：

后序最后一个元素 = 根

然后仍然使用中序：

左子树 | 根 | 右子树

去切分。

所以记忆：

前序找第一个根 后序找最后一个根 中序负责切左右

六、题型3：前序 + 后序，判断中序是否可能

例如：

前序：ABCD 后序：DCBA

这时候不能直接说“可以唯一还原”。

因为：

前序 + 后序 一般不能唯一确定二叉树

但我们可以根据它们判断树的大致结构。

前序：

A B C D

后序：

D C B A

二者正好互为逆序，这说明整棵树实际上退化成了一条链：

A | B | C | D

但是每一条边到底向左还是向右并不唯一。

例如：

A \ B \ C \ D

可以。

下面这样也可以：

A / B / C / D

甚至左右可以混合。

所以：

前序 + 后序确定的是“结点先后关系”， 但不一定确定每个单孩子结点的左右方向。

七、怎么判断中序序列可能/不可能

继续以上例：

前序：ABCD 后序：DCBA

可能出现的中序并不是任意排列。

对于这棵单链树，每一个结点只有一个孩子。

如果孩子是左孩子：

中序 = 子树 + 根

如果孩子是右孩子：

中序 = 根 + 子树

所以可以递归地产生合法中序。

例如可能出现：

ABCD BCDA DCBA CDBA

但：

CBDA

无法通过这种“单链左右选择”产生，因此不可能。

这类题的技巧是：

前序+后序若互逆 -> 先判断为单链结构 -> 再逐项验证中序是否能由“左挂/右挂”得到

八、题型4：前序和后序正好相反，树满足什么条件

这是性质判断题。

若：

前序：A B C D 后序：D C B A

则说明每个结点至多只有一个孩子。

因为只要某个结点同时拥有左、右两个孩子，前序和后序中左右子树的整体顺序关系就不可能完全互逆。

所以这种树会退化成一条链。

如果共有 n 个结点：

树高 = n

因此遇到题目：

若二叉树前序遍历和后序遍历正好相反， 则该树满足什么条件？

优先想到：

退化成单链 -> 高度 = 结点数

注意：

不能说“所有结点都没有左孩子” 也不能说“所有结点都没有右孩子”

因为链既可以向左，也可以向右，还可能左右混合。

九、为什么“前序 + 后序”一般不能唯一确定

看最简单的例子：

前序：AB 后序：BA

可能是：

A / B

也可能是：

A \ B

两棵树：

前序都为 AB 后序都为 BA

所以不能唯一确定。

真正缺少的信息就是：

B 是左孩子还是右孩子？

这也是所有“前序+后序不唯一”问题的本质。

十、考试中最常见的三类题

1. 已知前序 + 中序，求后序

固定：

前序找根 中序切分 递归

2. 已知后序 + 中序，求前序

固定：

后序最后找根 中序切分 递归

3. 已知前序 + 后序，判断可能性

第一反应：

一般不能唯一确定

然后再看题目是否有特殊条件。

例如：

前序和后序互逆

马上联想到：

单链树 高度 = 结点数

十一、选择题秒杀技巧

技巧1：有中序，先切

不要先画整棵树。

先写：

左子树 | 根 | 右子树

很多题直接就出来了。

技巧2：前序看头，后序看尾

前序第一个 = 根 后序最后一个 = 根

这是最稳定的定位方法。

技巧3：前序 + 后序先判断“不唯一”

除非题目额外给条件，否则：

前序 + 后序

不要直接唯一还原。

技巧4：前后互逆，先想“链”

看到：

前序：ABCD... 后序：...DCBA

先想到：

每个结点最多一个孩子

也就是：

树退化成链

十二、常见错误

错误1：把中序的第一个结点当根

错误。

中序不能直接确定根。

只有先知道根是谁，才能利用中序切左右。

错误2：看到前序+后序就开始唯一画树

错误。

前序+后序一般不唯一

错误3：前后互逆就认为只能全左或全右

错误。

左右方向可以混合。

真正确定的是：

每个结点至多只有一个孩子

错误4：切序列时只看字符，不看子树结点数量

例如中序切出：

左子树有3个结点

那么去切前序/后序时也必须严格取3个结点。

十三、考场统一流程

遇到遍历序列题，先问三个问题：

1. 根是谁？ 2. 能不能利用中序切左右？ 3. 这两种遍历能不能唯一确定？

然后分类：

前序+中序 -> 前序找根，中序切分 后序+中序 -> 后序找根，中序切分 前序+后序 -> 一般不唯一 -> 再根据题目额外条件判断

十四、10秒速记

前序：根左右 中序：左根右 后序：左右根 前序第一个是根 后序最后一个是根 前+中：唯一 后+中：唯一 前+后：一般不唯一 前后互逆： 树退化成链 高度 = 结点数

十五、最后只背三句话

先找根； 有中序就切分； 没中序一般不唯一。

这三句话基本覆盖408中绝大多数二叉树遍历序列选择题。