2026年 408 数据结构第3题 - 可视化解析

题目

已知二叉树 T 的中序遍历为 b, e, d, f, c, a, g，层序遍历为 a, b, g, c, d, e, f，则其后序遍历序列为（）。

先把 a 定为根、b 定为左子树根、g 定为右子树（叶子）这一步是对的；但在恢复 b 的右子树时，把 c 当成了"最左叶子"提前输出。实际 c 还要再往下分到 d-子树里，c 自己只能在 d-子树之后输出。把"祖先 c"和"叶子"的位置搞反了。

整体顺序对（左-右-根），但 c 被提前到了首位。可能的思路是：在层序里 c 出现得相当早（第 4 位），误以为 c 离根近就要先输出；或者把 c 当成 b 的左孩子输出。其实 c 是 b 的右子树根，必须先把 c 自己的左子树（含 d、e、f）走完，c 才能输出。

重建时把 g 的位置弄错了。中序里 a 是分界，其右只剩 g 一个，所以 g 必然是 a 的右孩子（且为叶子），在后序中应该出现在 a 之前一位（倒数第二）。选 D 把 g 插到了 e 和 f 之间，相当于把 g 错塞进 b 的子树，违反了中序里 g 在 a 之后这一约束。

重建步骤：

Step 1：层序首位是根，故 根 = a。在中序里以 a 切分：b, e, d, f, c | a | g。左子树中序 = b, e, d, f, c；右子树中序 = g。

Step 2：右子树中序只剩 g，所以右子树 = 单结点 g。

Step 3：在层序剩余 b, g, c, d, e, f 中，第一个属于左子树（即左子树根）的是 b。中序里 b 在最左 → b 没有左子树；右子树中序 = e, d, f, c。

Step 4：层序中接下来属于 b-右子树的第一个是 c（g 已被右子树拿走，c 在 d/e/f 之前）。在中序 e, d, f, c 里 c 在最右 → c 没有右子树；左子树中序 = e, d, f。

Step 5：层序里接下来出现的是 d（在 e、f 之前）。在中序 e, d, f 里 d 居中 → d 的左孩子 = e，右孩子 = f。

重建出的二叉树：

后序遍历（左-右-根）按子树分块：

最终答案是 C（e, f, d, c, b, g, a）。