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

A. c, e, d, f, b, g, a B. c, e, f, d, b, g, a C. e, f, d, c, b, g, a D. e, g, f, d, b, c, a

[tag_link]

正确答案：C

**【解析】**首先，根据层序遍历序列a,b,g,c,d,e,f可知根节点为a。结合中序遍历b,e,d,f,c,a,g，确定左子树包含节点b,e,d,f,c，右子树仅包含g。左子树的层序序列为b,c,d,e,f，中序序列为b,e,d,f,c，因此左子树的根为b。由于b在中序中为首，故无左子树，其右子树的根为层序中下一个节点c。对于以c为根的子树，中序为e,d,f,c，故c无右子树，其左子树的根为层序中的d。对于以d为根的子树，中序为e,d,f，故d的左子节点为e，右子节点为f。因此树的结构为：

• a的左子节点为b，右子节点为g；
• b的左子节点为空，右子节点为c；
• c的左子节点为d，右子节点为空；
• d的左子节点为e，右子节点为f。后序遍历顺序为：左子树的后序、右子树的后序、根节点。左子树的后序依次为e,f,d,c,b，右子树的后序为g，根为a，故后序遍历序列为e,f,d,c,b,g,a，对应选项 C。