2017年 408 数据结构第5题 - 可视化解析

题目

已知一棵二叉树的树形如下图所示，其后序序列为 e, a, c, b, d, g, f，树中与结点 a 同层的结点是( )。

编号仅为表述方便（按层序遍历自顶向下、自左向右标注），原题节点皆为空圆。结构特征：根有左右两个孩子；左孩子只有右子，且其右子只有左子；右孩子只有左子，且其左子只有右子。共 7 个节点，分布在 4 层（1 / 2 / 2 / 2）。

把"父节点"误当成"同层"。沿着图里 a 所在的左半枝看，c 是 a 的父节点（在第 2 层），不是同层。这种错往往出在没把每一层的成员清晰列出来，只盯住"靠近"二字。

f 是根，独占第 1 层，任何节点都不可能与它同层（除了它自己）。选 C 多半是后序还原失败：误以为后序的最末位不一定是根，或者干脆把节点 a 的层数也搞错了。

把"对称位置"当成"同层"。在图里 c 和 g 是第 2 层的左右对称兄弟；a 在 c 下方一层（第 3 层），和它对称的应该是 g 下方那一层的节点（即 d），而不是 g 本身。看图直接对称取节点是这道题的高频陷阱。

思路：先用后序序列还原节点字母与图中位置的对应关系，再读出 a 所在的层。

Step 1：根从后序末位读出

后序遍历规则是 左子树 → 右子树 → 根，因此后序的最后一个元素必为整棵树的根：

Step 2：按图的形状切分左右子树

看图：根的左子树有 3 个节点（左枝 1 → 2 → 4 → 6），右子树也有 3 个节点（右枝 1 → 3 → 5 → 7）。所以后序的前 3 个属于左子树，中间 3 个属于右子树，末位是根：

Step 3：递归还原每个子树

左子树后序 e, a, c → 子树根是 c（c 是根 f 的左孩子）。看图，c 没有左子，只有右子；那么 e, a 全在 c 的右子树里。再用同规则：右子树后序末位是 a，所以 c 的右孩子是 a；剩下的 e 是 a 的左孩子。

右子树后序 b, d, g → 子树根是 g（g 是根 f 的右孩子）。看图，g 没有右子，只有左子；b, d 都在 g 的左子树里。左子树后序末位是 d，所以 g 的左孩子是 d；剩下的 b 是 d 的右孩子。

Step 4：把字母写回图里

逐层列表：

Step 5：读结果

a 在第 3 层。第 3 层的另一个节点是 d。

最终答案是 B（d）。