CSP-J 入门级 · CSP 2024 入门级第一轮 第 12 题

已知二叉树的前序遍历为 $[A, B, D, E, C, F, G]$，中序遍历为 $[D, B, E, A, F, C, G]$，请问该二叉树的后序遍历结果是？（ ）

这题就是考二叉树遍历的逆向还原。拿到前序和中序，先找前序第一个定根，再去中序里把树切成左右两半，然后递归套娃，最后按后序（左右根）输出序列。

学生最容易栽跟头在两步：一是把前序和中序搞反，以为前序是左根右、中序是根左右，这样切分出来的子树顺序全错；二是切分后没看清前序里紧接着的是左子树的根，直接当成右子树去切，导致左右子树角色互换。还有一种是递归到底时，把叶子节点的左右孩子位置搞混，最后后序遍历的顺序就颠倒了。

还原二叉树

前序（根左右）：[A, B, D, E, C, F, G] 中序（左根右）：[D, B, E, A, F, C, G]

第 1 步：确定根

前序第一个元素 A 是根。 中序里 A 左边 [D,B,E] 是左子树，右边 [F,C,G] 是右子树。