NOIP 普及组初赛 · NOIP 2008 普及组初赛试题 第 13 题

二叉树 $T$，已知其先根遍历是 $\texttt{1 2 4 3 5 7 6}$（数字为结点的编号，以下同），中根遍历是 $\texttt{2 4 1 5 7 3 6}$，则该二叉树的后根遍历是（ ）。

拿到题先别急着算，把先序和中序摆一起看：先序定根，中序定左右子树范围。根是1，中序里1左边是左子树，右边是右子树，然后递归套娃，最后按左-右-根的顺序输出后序，答案自然出来。

最容易栽跟头的地方是：1）把先序和中序搞反，以为先序里1后面紧跟着的是左子树根，其实那是先序里的第二个节点，得去中序里找1的位置才能划界；2）递归时左右子树的节点数数错，比如把右子树当成只有两个节点，导致后序里7和5的顺序颠倒；3）后序遍历顺序记混成左-根-右，那样就会把根1提前输出，直接掉进C或D的坑里。

二叉树遍历重建与后序输出

考点与概念

这题考的是二叉树三种遍历的对应关系：

• 先序（根左右）：第一个一定是根；
• 中序（左根右）：根把序列切成左右两部分；
• 后序（左右根）：最后才是根。

命题人常在这里挖坑：先序和中序都能唯一确定一棵二叉树，但学生容易把“先序里根后面的节点”误当成左子树根，或者在中序里找错根的位置，导致左右子树划分错误。递归重建时，节点数数错也会让后序顺序全乱。