重建二叉树（C++）

目录

1 问题描述

1.1 示例1

1.2 示例2

1.3 示例3

2 解题思路

3 代码实现

4 代码解析

4.1 初始化

4.2 递归部分

4.3 主逻辑

5 总结

---

1 问题描述

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围：n≤2000n≤2000，节点的值 −10000≤val≤10000−10000≤val≤10000

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

1.1 示例1

输入：

[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

返回值：

{1,2,3,4,#,5,6,#,7,#,#,8} 

1.2 示例2

输入：

[1],[1]

返回值：

{1}

1.3 示例3

输入：

[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]

返回值：

{1,2,5,3,4,6,7}

2 解题思路

首先，我们通过中序遍历构建一个哈希表，将每个节点值与其在中序遍历中的索引进行映射，这样可以在构建树时快速定位每个节点的左右子树范围。然后，利用递归的方式构建树。在递归过程中，前序遍历的第一个元素为当前子树的根节点，根据根节点在中序遍历中的位置可以划分左右子树的范围。每次递归调用时，分别构建左右子树，直到树的叶子节点（即子树为空）为止。最终，递归返回构建好的二叉树。

3 代码实现

/*** struct TreeNode {*  int val;*  struct TreeNode *left;*  struct TreeNode *right;*  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
#include <unordered_map>
#include <vector>
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param preOrder int整型vector* @param vinOrder int整型vector* @return TreeNode类*/unordered_map<int, int> indexMap;TreeNode* buildTree(vector<int>& preOrder, int preStart, int preEnd, vector<int>& vinOrder, int inStrat, int inEnd) {if (preStart > preEnd) return nullptr;int rootVal = preOrder[preStart];TreeNode* root = new TreeNode(rootVal);int rootIndex = indexMap[rootVal];int leftSize = rootIndex - inStrat;root->left = buildTree(preOrder, preStart + 1, preStart + leftSize, vinOrder, inStrat, rootIndex - 1);root->right = buildTree(preOrder, preStart + leftSize + 1, preEnd, vinOrder, rootIndex + 1, inEnd);return root;}TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {// write code hereint n = preOrder.size();for (int i = 0; i < n; i++){indexMap[vinOrder[i]] = i;}return buildTree(preOrder, 0, n - 1, vinOrder, 0, n - 1);}
};

4 代码解析

4.1 初始化

unordered_map<int, int> indexMap;

首先定义了一个 unordered_map<int, int> 类型的 indexMap，该映射用来存储中序遍历数组中每个节点值的索引位置。这种做法能够在递归过程中快速查找某个节点在中序遍历中的位置，避免了每次都遍历中序数组，从而提高了算法的效率。

4.2 递归部分

TreeNode* buildTree(vector<int>& preOrder, int preStart, int preEnd, vector<int>& vinOrder, int inStrat, int inEnd) {if (preStart > preEnd) return nullptr;int rootVal = preOrder[preStart];TreeNode* root = new TreeNode(rootVal);int rootIndex = indexMap[rootVal];int leftSize = rootIndex - inStrat;root->left = buildTree(preOrder, preStart + 1, preStart + leftSize, vinOrder, inStrat, rootIndex - 1);root->right = buildTree(preOrder, preStart + leftSize + 1, preEnd, vinOrder, rootIndex + 1, inEnd);return root;
}

在 buildTree 函数中，递归的基础条件是 preStart > preEnd，此时表示当前子树没有节点，返回 nullptr。通过前序遍历数组的 preStart 位置来获取根节点的值 rootVal。接着，利用 indexMap 快速查找该根节点在中序遍历中的位置 rootIndex，并根据该位置确定左子树的大小 leftSize。然后递归构建左子树和右子树，分别处理前序和中序遍历数组中的相应部分，最后返回当前根节点。

4.3 主逻辑

TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {int n = preOrder.size();for (int i = 0; i < n; i++) {indexMap[vinOrder[i]] = i;}return buildTree(preOrder, 0, n - 1, vinOrder, 0, n - 1);
}

在 reConstructBinaryTree 函数中，首先通过一个循环填充 indexMap，它记录了中序遍历中每个节点值的索引。这一步为后续的递归过程提供了高效的查找支持。然后，调用 buildTree 函数开始递归构建二叉树，传入前序遍历和中序遍历的整个范围，最终返回构建完成的二叉树的根节点。 

5 总结

该算法使用前序遍历和中序遍历的特点，通过递归重建二叉树。在每一步中，通过根节点在中序遍历中的位置来划分左子树和右子树，避免了不必要的遍历。unordered_map 提供了 O(1) 时间复杂度的查找功能，使得整体算法在时间和空间上的效率都得到了保证。整个算法的时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是二叉树的节点数量。