从26考研408数据结构一道真题出发,深入探讨二叉树的遍历问题

大家好，我是「阑梦清川」

今天，我们通过2026年408考研数据结构中的一个“二叉树遍历”题目，来深入探讨一下这类题目的做法。

我们知道，二叉树有三种遍历方式，分别是：

1. 前序遍历
2. 「中序遍历」
3. 后序遍历

这种题目无论是在我们日常的本科专业课学习，还是在考研过程中，其实都是非常重要的。我们之前都学过，它本身并不是很难，难点可能在于如何根据两种遍历结果推出另外一种遍历方式（这需要掌握一定的方式和方法）。

题目非常简单：给一个二叉树的「中序遍历和层序遍历」，让我们推导它的后序遍历。

相关的前提知识如下：

1. 「层序遍历」：就是一层一层地访问，这个很好理解。
2. 中序遍历：访问顺序是"左、中、右"。
3. 后序遍历：访问顺序是"左、右、中"。

我们要按照这样的逻辑顺序，去对二叉树进行遍历。

我第一次看到这个题目时，在草稿本上画了很久。

其实第一步比较好想，即根据「层序遍历确定 A 是根节点」，然后观察中序遍历的结果。你会发现 A 将序列分为左、右两部分：

1. 左边是 BEDFC，由此确定 A 的左子树包含这些节点
2. 右边是 G，由此确定 A 的右子树就是 G

当时我不断在草稿本上尝试推演这五种对应的情况，试图让它们符合层序遍历的过程以及最终结果，确实推演了很久。

但今天我发现，这实际上是一种错误或比较浪费时间的方式。虽然我最终把答案推导出来了，但我总觉得这背后肯定隐藏着一些更高效的技巧和方法。

首先上面这个推断出来 A 是根节点，左子树和右子树对应的内容是什么？

这个是「破题点」，大家一定是可以想到的，应该大部分人都没有问题。

关键就是左子树 B、E、D、F、C 它们是如何分布的，以及它们之间的关系。这一步确实比较复杂。

我当时画了好几种可能存在的情况，通过不断排除、不断与层序遍历（Level-order Traversal）去核对，才得出结论。但最正确的方式应当是将两者结合起来看。

下面我介绍一种「更科学、更快速」的解题方式：

在「层序遍历」里面，左子树的节点 BEDFC 中「最先出现的是 B，所以 B 就是左子树的根节点」。

这样我们就构建出来了第一层。

a / \b   g

接下来我们继续分析 B 下面的子树情况。

继续回到「中序遍历」，左子树部分是 BEDFC。我们知道 B 是这个子树的根节点，按照刚才的方法，B 的左子树是空的，说明 EDFC 都在它的「右子树」上面。

所以，现在这个树长成下面这个样子：

a / \b   g \(e,d,f,c 在这里面)

接下来我们继续使用同样的方法。B的右子树包含了E、D、F、C四个节点，我们需要找出这个子树的根节点。

这个时候，我们继续回到「层序遍历」：A、B、G、C、D、E、F。在E、D、F、C四个节点中，「C是最先出现的，所以C就是这四个节点里面的根节点」。

因此，现在的树就是下面的这个样子：

a / \b   g \  c /

  (e,d,f 在这里面)

现在我们继续来看 C 的子树。

B 的右子树节点是 EDFC，现在我们用 C 把这个序列「破开」，发现 C 只有「左子树」（也就是只有左边的部分 EDF）。

因此，现在树变得更加完整了，成为了下面的样子：

a / \b   g \  c /

   (e,d,f)

在这个里面，C的左子树包含了 E、D、F，我们需要找到这个子树的根。

老办法，我们继续回到「层序遍历」：

1. 我们发现在 E、D、F 三个节点里面，「D 是最先出现的」
2. 「所以 D 就是 C 的左子树的根节点」

最后用 D 把 DEF 这个序列「破开」：

1. D 的左子树是 E
2. D 的右子树是 F

所以整棵树的构建就完成了

    a   / \  b   g\    c   /  d / \e   f

二叉树构建完成之后，它的「后序遍历」就变得显而易见了。

按照以下顺序得到最终的结果：

1. 先访问左子树
2. 再访问右子树
3. 最后访问「根节点」

通过这个题目，我们能够得到的一点理解和体会是：

1. 如果使用传统方式，你需要不断地根据中序遍历和层序遍历，在草稿上划算出它可能存在的情况。这个过程虽然可能是正确的，但会非常耗费时间。
2. 如果你使用这种方式，「不断地在中序遍历和层序遍历的基础上进行推演」，「每推出它的根节点，再回到题目已知条件上继续往下推演」，这样效率就会更高一些。