使用给定的中序和前序遍历构建树

引言

树的遍历算法是理解和重构二叉树的基础。给定二叉树的中序和前序遍历，可以重建原始二叉树。这个过程涉及利用这些遍历的特性来准确地重建树结构。

理解中序和前序遍历

中序和前序遍历是用于遍历和显示二叉树节点的方法。

中序遍历

在中序遍历中，我们先访问左子树，然后是根节点，最后是右子树。

对于二叉树，中序遍历会产生一个排序的节点值序列。

前序遍历

在前序遍历中，我们先访问根节点，然后是左子树，最后是右子树。

前序遍历对于重建树结构至关重要。

考虑以下二叉树

该树的中序遍历为 4-2-5-1-3，前序遍历为 1-2-4-5-3。

重建过程

给定中序和前序遍历，可以重建原始二叉树。关键在于理解每种遍历方法的特性及其与树结构的关系。

以下是从中序和前序遍历构建二叉树的步骤：

步骤：

• 确定根节点：在前序遍历中，遇到的第一个元素始终是根节点。
• 在中序遍历中定位根节点：使用上一步获得的值（根节点），找到它在中序遍历中的索引。该索引在中序遍历中分隔左子树和右子树。
• 递归处理子树：根据在中序遍历中找到的索引，我们可以确定左子树和右子树的大小。对左子树和右子树递归地重复上述步骤。

分步构建示例

让我们以二叉树的中序和前序遍历为例：

中序：[D, B, E, A, F, C]

前序：[A, B, D, E, C, F]

• 选择根节点

根节点是 'A'（前序遍历中的第一个元素）。

• 在中序遍历中找到根节点

'A' 在中序遍历中的位置是 3。

• 递归构建左子树和右子树

对于左子树：中序 [D, B, E]，前序 [B, D, E]

对于右子树：中序 [F, C]，前序 [C, F]

对每个子树重复此过程，直到整个树构建完成。

实施

说明

• 二叉树使用 TreeNode 结构定义，构建逻辑在 Solution 类中实现。
• 在 Solution 类中，buildTree 方法负责启动构建过程。它接受两个向量作为输入参数：preorder，代表二叉树的前序遍历；inorder，代表中序遍历。
• 该方法使用一个名为 indexMap 的无序映射来有效地存储中序遍历中元素的索引，以便在树构建过程中快速查找。
• 二叉树的实际构建由 buildTreeHelper 方法执行，这是一个递归函数，它接受前序和中序遍历的当前片段以及索引映射。
• 此辅助函数使用前序遍历的第一个元素构建当前子树的根节点。
• 然后，它通过查找根值在中序序列中的索引来确定左子树的大小。递归地，根据遍历的相应片段构建左子树和右子树。
• inorderTraversal 函数用于验证，它对构建的树进行中序遍历。
• 在 main 函数中，创建 Solution 类的一个实例，并使用示例前序和中序遍历调用 buildTree 方法。
• 然后将构建的二叉树的中序遍历打印到控制台，以验证树是否已正确构建。

程序输出

优化后的带哈希的递归解决方案

为了优化上述递归解决方案，我们可以使用哈希表来存储中序遍历中元素的索引。这样就无需线性搜索来查找根在中序遍历中的位置。

说明

• 二叉树使用 TreeNode 结构表示，该结构具有整数值，左子节点指针（left）和右子节点指针（right）。
• 主函数 buildTree 接受两个向量作为输入：preorder 代表二叉树的前序遍历，inorder 代表中序遍历。
• 该函数根据这些遍历构建并返回二叉树。它使用一个辅助函数 buildTreeHelper，该函数使用输入向量提供的索引和映射递归地构建树。
• buildTreeHelper 函数接受前序和中序遍历的当前索引范围（preStart, preEnd, inStart, inEnd）以及一个映射（inorderMap），该映射存储值到其中序遍历中索引的映射。
• 基本情况检查范围是否无效，无效则返回 nullptr。否则，它创建一个具有当前前序索引（preStart）的值的新节点，并根据计算出的索引递归地构建其左子树和右子树。
• printInorder 函数是一个简单的实用函数，用于对构建的二叉树进行中序遍历并将值打印到控制台。它在 main 函数中用于显示构建树的中序遍历。
• 在 main 函数中，提供了两个示例向量 preorder 和 inorder 来演示 buildTree 的用法。
• 使用 printInorder 函数打印构建的树，显示二叉树的中序遍历。

程序输出

结论

总之，从给定的中序和前序遍历构建树的问题是计算机科学中的一个经典挑战，涉及根据节点的给定顺序重建二叉树。

中序遍历描绘了访问节点的顺序，而前序遍历提供了从根开始的探索顺序。解决此问题需要系统的方法来识别根、左子树和右子树，从而能够重建原始二叉树。

一个关键的观察是，前序遍历中的第一个元素始终是树的根。通过在中序遍历中找到此根，我们可以确定左子树和右子树的位置。这一见解构成了构建整个二叉树的递归算法的基础。随着算法的进行，它将问题分解为更小的子问题，直到整个树被重建。这种递归方法利用了遍历中固有的结构，并以与节点数量成比例的时间复杂度有效地重建了二叉树。