题目

给定二叉树如下图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列是 3，1，7，5，6，2，4，则其遍历方式是( )。

错因

A

LRN 是后序遍历（左→右→根）。对该树实际跑一遍后序：左子树后序为 4,6,7,5,2，右子树后序为 3，根为 1，得 4,6,7,5,2,3,1。与给定序列 3,1,7,5,6,2,4 完全不同，选 A 是没有实际验证就凭感觉选了后序。

B

NRL 是先根再右再左（根→右→左）。对该树跑 NRL：根 1，右子树 3，左子树 NRL(2)=2,5,7,6,4，得 1,3,2,5,7,6,4。与给定序列不符，选 B 是把"先访问右边再访问根"和"先访问根再访问右边"搞混了。

C

RLN 是右→左→根。对该树跑 RLN：右子树 3，左子树 RLN(2)=7,6,5,4,2，根 1，得 3,7,6,5,4,2,1。与给定序列仅相差左子树内部的顺序，选 C 是把 RNL 和 RLN 混淆，忘了 RNL 是"右→根→左"而非"右→左→根"。

总解析

题目给定树（括号语法 根(左, 右)）：

尝试 RNL（右→根→左）遍历，从根 1 出发：

• 先访问右子树：右孩子 3 为叶 → 输出 3
• 访问根：输出 1
• 访问左子树（根为 2），对节点 2 递归 RNL：
  • 先访问 2 的右子树（根为 5），对节点 5 递归 RNL：
    • 右孩子 7 为叶 → 输出 7
    • 根 → 输出 5
    • 左孩子 6 为叶 → 输出 6
  • 访问根 2 → 输出 2
  • 访问左孩子 4（叶）→ 输出 4

得序列 3, 1, 7, 5, 6, 2, 4，与题目完全吻合。答案 D（RNL）。