给定两个遍历序列，你能构建二叉树吗？

二叉树是用于分层组织数据的基本数据结构。它们在计算机科学中有许多应用，从在二叉搜索树中存储排序数据到表示表达式解析树。

二叉树的一个关键方面是如何遍历它们——系统地访问每个节点以处理或打印其包含的数据。最常见的三种遍历方法是中序、前序和后序，每种方法产生不同的节点访问顺序。

给定二叉树中的节点值，我们可以使用这些技术遍历它并获得访问节点的序列。一个有趣的问题是，如果我们只知道遍历序列，能否唯一地重建原始二叉树？

本文探讨了从二叉树的中序和前序（或后序）遍历序列重建二叉树的算法。我们讨论了不同的遍历序列如何编码有关树结构和节点关系的信息。提出了一种高效的 O(n^2) 算法，该算法递归地分割遍历以构建左子树和右子树，从而构建原始树。

能够从遍历结果重建二叉树在几种情况下都很有用。它有助于从遍历数据中恢复树结构。它还提供了对不同遍历技术特性的见解。这个算法问题展示了如何系统地处理和分析复杂的树结构。

中序遍历

中序遍历涉及先遍历左子树，然后访问根节点，最后遍历右子树。例如，对于二叉树

• 从最左边的节点开始，一直递归地向左，直到到达叶子节点
• 访问叶子节点（打印它）
• 转到叶子的父节点，打印它，然后转到右子节点
• 递归地继续此过程——向左，访问，向右
• 按升序打印节点

例如，对于二叉树

中序遍历打印：4 2 5 1 3

在中序遍历中，根节点在子树之间被访问，因此遍历倾向于产生排序的输出。

用途：产生排序输出，因此对二叉搜索树很有帮助。

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后是右子树。对于示例树，前序顺序将是：A、B、D、E、C

在前序遍历中，在访问子树之前先访问根节点。

• 从根节点开始，打印它
• 递归地转到左子树，打印左子节点
• 完成左子树后，递归地访问右子树
• 在子节点之前打印父节点

对于同一示例树，前序遍历打印：1 2 4 5 3

用途：创建树的副本，有助于从遍历顺序构建树

后序遍历

后序遍历涉及先遍历左子树，然后遍历右子树，最后访问根节点。对于同一示例树，后序遍历顺序将是：D E B C A

在后序遍历中，在访问完子树后才访问根节点。

• 从最左边的节点开始，一直向左，然后打印叶子节点
• 转到叶子的右兄弟，向下递归打印
• 两个子树都完成后，打印父节点
• 在子节点之后打印父节点

对于示例，后序是：4 5 2 3 1

用途：安全地删除树节点，计算带括号的表达式

层序遍历

层序遍历从左到右逐层访问树节点。对于示例树，层序遍历将是 A B C D E。

节点按它们在树中深度或级别的递增顺序访问。层序遍历使用队列来遍历树。

• 逐层从左到右打印节点
• 使用队列来跟踪节点
• 从队列中出队一个节点，打印它，然后将其子节点入队
• 继续，直到队列为空

对于示例，层序遍历打印：1 2 3 4 5

用途：打印层级结构，用于广度优先搜索

形成二叉树的算法

二叉树的三种标准遍历方法是中序、前序和后序遍历。中序遍历访问左子树、根节点和右子树。前序遍历首先访问根节点，然后是左子树和右子树。后序遍历访问左子树、右子树和根节点。

在这三种遍历序列中，任意两个都可以用来唯一地构造原始二叉树。这是因为中序遍历按排序顺序给出节点值，而前序和后序则编码根节点相对于其子树的位置。

给定中序和前序遍历来重建二叉树的算法如下：

1. 取前序遍历的第一个元素。这是树的根节点。
2. 在中序遍历序列中搜索该节点值的位置。
3. 在中序遍历中出现在该节点之前的元素属于左子树，出现在其之后的元素属于右子树。
4. 通过取中序遍历中根节点之前的子序列和前序遍历中对应的子序列，递归地构造左子树。
5. 通过取中序遍历中根节点之后的子序列和前序遍历中对应的子序列，递归地构造右子树。
6. 返回带有正确附加的左子树和右子树的根节点。

例如，考虑一个中序遍历为 DBEAFC 且前序遍历为 ABCDEF 的二叉树。

前序的第一个元素是 A——这是根节点。在中序中，DBE 属于 A 的左子树，CEF 属于 A 的右子树。我们使用中序中的子序列 DBE 和前序中的 ABC 递归地构造左子树。这给了我们左子树。右子树使用中序中的 EF 和前序中的 DEF 构建。通过将左子树和右子树附加到 A，我们得到原始二叉树。

此算法的时间复杂度为 O(n^2)，因为在中序中找到根节点分区需要 O(n) 时间，并且我们对 O(n) 个节点重复此操作。空间复杂度为 O(n)，用于递归栈。使用中序和后序序列也适用类似的重建过程。

以下是给定中序和后序遍历序列重建二叉树的步骤：

1. 取后序序列的最后一个元素。这是树的根节点。
2. 在中序序列中搜索该节点值的位置。
3. 在中序遍历中出现在该节点之前的元素属于左子树，出现在其之后的元素属于右子树。
4. 通过取中序中根节点之后的子序列和后序中对应的子序列（不包括作为根的最后一个元素），递归地构造右子树。
5. 通过取中序和后序中根节点之前的子序列，递归地构造左子树。
6. 返回带有正确附加的右子树和左子树的根节点。

使用中序和前序之间的关键区别是：

• 我们取后序的最后一个元素而不是前序的第一个元素来获取根节点。
• 我们先递归构造右子树，再构造左子树，因为后序遍历先访问右子树。

例如，如果中序序列是 DBEAFC 且后序序列是 DEBFCA，那么

• 后序的最后一个元素是 A，这是根节点。
• 在中序中，DBE 是 A 的左子树，CEF 是 A 的右子树。
• 通过递归调用算法，使用中序中的 EF 和后序中的 EBF 来构造右子树。
• 使用中序和后序中的 DBE 来构造左子树。
• 返回根节点 A，并附加左子树和右子树。

这可以从二叉树的中序和后序遍历中重建原始二叉树。总的时间和空间复杂度与使用中序和前序的复杂度相同。

总之，给定任意两个中序、前序和后序遍历，我们可以唯一地重建原始二叉树。关键在于使用一个序列（中序）来识别节点关系，并使用另一个序列中的根节点位置来系统地递归构建子树。这表明不同的遍历方法如何编码二叉树结构的互补信息。