前序遍历与中序遍历重建二叉树解法

在IT技术领域，遇到的一个常见的算法问题是关于二叉树的重建。题目要求根据一棵二叉树的前序遍历（Preorder Traversal）和中序遍历（Inorder Traversal）结果来重构该树。前序遍历的顺序是根节点 -> 左子树 -> 右子树，而中序遍历则是左子树 -> 根节点 -> 右子树。这两个序列对于构建树至关重要，因为它们包含了关于树结构的关键信息。 具体来说，给定的题目中，前序遍历 `[3, 9, 20, 15, 7]` 表示树的根节点为3，然后依次是左子树的根9，接着是左子树的左子树20，然后是右子树的根15，最后是右子树的右子树7。中序遍历 `[9, 3, 15, 20, 7]` 则揭示了节点在树中的相对位置。通过这两个序列，我们可以确定每个节点的位置，并按照二叉树的规则构造出完整的树形结构。 解题的关键在于实现一个递归函数 `dfs`（深度优先搜索），它接受前序遍历、中序遍历以及它们的起始和结束索引。首先，创建一个哈希表 `pos` 用于存储中序遍历中每个节点在原数组中的位置。接着，调用 `dfs` 函数，参数分别为前序遍历、中序遍历的数组、当前处理的前序序列起始位置、结束位置，以及对应的中序遍历的起始和结束位置。 `dfs` 函数的逻辑如下： 1. 如果前序序列的起始位置大于结束位置，说明已经处理完一个子树，返回 `NULL`。 2. 找到前序序列中当前节点在中序遍历中的位置 `k`，这将帮助我们区分左子树和右子树。 3. 创建一个新的节点 `root`，其值为前序序列的当前节点。 4. 递归地构建左子树，调用 `dfs` 函数，传入更新后的前序序列、中序序列和起始位置。 5. 递归地构建右子树，同样更新前序序列和中序序列的起始位置。 6. 返回根节点 `root`，完成当前子树的构建。 参考答案中给出的 `Solution` 类定义了一个名为 `buildTree` 的公共方法，使用 `unordered_map` 和 `dfs` 函数来实现这个功能。通过这种方式，可以高效地根据给定的前序和中序遍历重建二叉树。 总结来说，这个算法问题主要考察的是二叉树遍历的理解以及如何利用这些遍历来重构树结构。在实际编程中，解决此类问题有助于提高数据结构和算法的运用能力，尤其是在处理复杂的数据结构问题时。