NOIP 普及组初赛 · NOIP 2007 普及组初赛试题 第 20 题

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

拿到两个遍历序列，先根的第一个数1就是根，立刻在中根里把1切开，左边4个数是左子树，右边2个数是右子树，然后按左子树节点数去先根里切，递归下去就能还原整棵树，最后按左→右→根输出后根序列即可。

最容易栽跟头的地方是：把先根和中根的对应关系搞混，以为先根里跟着根后面的几个数就是左子树，其实必须先数中根里左子树到底有几个节点，再回头去先根里数同样个数。另外，构建子树时容易把左右子树的范围切偏，比如把中根里根右边的数当成左子树的一部分，或者在先根里多切少切。还有，后根遍历的最后一个数必须是整棵树的根，如果算出来不是1，那肯定哪里错了。最后，还原出来的树结构一定要画出来，边看边填，否则很容易在递归几层后迷失方向，把选项B或D这种看着像但顺序不对的坑给踩了。

这道题考的是二叉树的遍历与还原，核心知识点就是：已知先根（前序）和中根（中序）遍历序列，如何唯一确定一棵二叉树，进而写出后根（后序）遍历序列。概念上，先根是根→左→右，中根是左→根→右，后根是左→右→根。还原的思路非常清晰：先根的第一个节点永远是整棵树的根；在中根里找到这个根，它左边全是左子树的节点，右边全是右子树的节点；数一下左子树有几个节点，再回头去先根里，根后面紧跟着的那一段（同样长度）就是左子树的先根序列，剩下的就是右子树的先根；然后对左子树和右子树递归重复这个过程。最后，按后根规则输出：先输出左子树的后根，再输出右子树的后根，最后输出根节点。

命题人特别喜欢在这种题里挖三个坑：一是让你直接默写后根序列而不还原树，这时候如果左右子树范围数错，后根顺序就全乱；二是选项里故意把某些子树的后根顺序颠倒，比如把右子树的后根提前或延后，诱导你只看局部不看整体；三是让你只还原左子树或右子树，然后让你判断某个节点的位置，这时候如果中根里根的位置找错，整个结构就歪了。这道题就是典型的第一类坑，直接让你求后根，但选项A和B、D非常接近，B把根1提前了，D把3和2的位置搞混了，都是容易因递归时切分错误而掉进去的。

现在咱们一步步来推。已知先根：1 2 4 5 6 3 7；中根：4 2 6 5 1 7 3。

第一步，先根第一个数是1，所以根是1。在中根里找1，它左边是[4, 2, 6, 5]，共4个数，说明左子树有4个节点；右边是[7, 3]，共2个数，说明右子树有2个节点。

第二步，处理左子树。左子树的先根序列是根1后面的前4个数：[2, 4, 5, 6]；左子树的中根序列就是刚才切出来的[4, 2, 6, 5]。左子树的根是2。在中根[4, 2, 6, 5]里找2，左边是[4]，1个数，说明2的左孩子是4；右边是[6, 5]，2个数，说明2的右子树有2个节点。

第三步，处理2的左孩子。先根里2后面紧跟的是4，中根里2左边也是4，所以4是叶子节点，无左右孩子。

第四步，处理2的右子树。先根里2后面、4后面的部分是[5, 6]；中根里2右边是[6, 5]。右子树的根是5。在中根[6, 5]里找5，左边是[6]，1个数，说明5的左孩子是6；右边为空，说明5无右孩子。6是叶子节点。

至此，左子树还原完毕：2的左孩子是4，右孩子是5，5的左孩子是6。

第五步，处理右子树。右子树的先根是[3, 7]；中根是[7, 3]。右子树的根是3。在中根[7, 3]里找3，左边是[7]，1个数，说明3的左孩子是7；右边为空，说明3无右孩子。7是叶子节点。

第六步，整棵树结构就出来了：根1，左子树是以2为根的树（2→左4，2→右5→左6），右子树是以3为根的树（3→左7）。

现在按后根遍历规则输出：先输出左子树的后根，再输出右子树的后根，最后输出根1。

左子树的后根：先处理2的左孩子4（输出4），再处理2的右子树（5的左孩子6输出6，5输出5），最后输出2。所以左子树后根是：4 6 5 2。

右子树的后根：先处理3的左孩子7（输出7），再处理3的右孩子（无），最后输出3。所以右子树后根是：7 3。

最后输出根1。

合起来就是：4 6 5 2 7 3 1。

对照选项，A选项正是这个序列，所以答案选A。

避坑提醒：做题时千万别只盯着数字顺序，一定要先还原树的结构，或者至少在心里把左右子树的节点数数清楚。这道题如果在中根里把1的位置看错，或者在先根里切左子树时多切了一个数，后面整个递归都会偏，最后算出的后根序列就会变成B或D那种‘看着像但顺序不对’的陷阱。记住，后根遍历的最后一个数必须是整棵树的根，如果算出来不是1，那就肯定哪里错了。