CSP-J 入门级 · CSP 2023 入门级第一轮 第 11 题

给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么?

这题核心就是还原二叉树。拿到前序和中序，第一反应是：前序头就是根，去中序里找这个根，左边全是左子树节点，右边全是右子树节点。然后对左右子树递归重复这个过程，最后按后序（左右根）输出即可。

学生最容易栽跟头在两个地方：一是把遍历顺序记混，前序是根左右、中序是左根右、后序是左右根，很多人会把后序当成左根右或者根左右，导致最后答案完全偏；二是还原树的时候，只盯着根节点，没看清左右子树各自的根是谁。比如左子树前序是 BDE，根是 B，但 B 在中序里排在最后，说明 D、E 都在 B 的左子树里，很多人会误以为 B 有右子树，或者把 E 当成 B 的右孩子，这样树结构就歪了，后序遍历自然就不对。还有人在分割子树时数错长度，把右子树当成左子树处理，这也是高频错误。

考点与概念

这题考查二叉树的三种遍历顺序及如何通过前序和中序唯一还原二叉树。前序遍历是“根左右”，中序是“左根右”，后序是“左右根”。记住这个口诀就能避免顺序混淆。

命题人怎么挖坑

命题人常在这里设两个坑：一是让你直接背遍历顺序，二是让你还原树。单纯背顺序很容易选错选项，但还原树需要一步步拆解。这道题就是典型的还原树题，它不直接问树长什么样，而是问后序遍历结果，逼你必须先还原树，再按后序输出。