目录
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 here
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);
}
};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 是二叉树的节点数量。