前序中序重建二叉树c++

以下是C++实现前序中序重建二叉树的代码和解释：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); i++) {
            inorder_map[inorder[i]] = i;
        }
        return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inorder_map);
    }

    TreeNode* buildTreeHelper(vector<int>& preorder, int pre_start, int pre_end, vector<int>& inorder, int in_start, int in_end, unordered_map<int, int>& inorder_map) {
        if (pre_start > pre_end || in_start > in_end) {
            return NULL;
        }
        int root_val = preorder[pre_start];
        TreeNode* root = new TreeNode(root_val);
        int inorder_root_index = inorder_map[root_val];
        int left_subtree_size = inorder_root_index - in_start;
        root->left = buildTreeHelper(preorder, pre_start + 1, pre_start + left_subtree_size, inorder, in_start, inorder_root_index - 1, inorder_map);
        root->right = buildTreeHelper(preorder, pre_start + left_subtree_size + 1, pre_end, inorder, inorder_root_index + 1, in_end, inorder_map);
        return root;
    }
};

int main() {
    vector<int> preorder = {3, 9, 20, 15, 7};
    vector<int> inorder = {9, 3, 15, 20, 7};
    Solution s;
    TreeNode* root = s.buildTree(preorder, inorder);
    return 0;
}

解释：

1. 首先定义二叉树的结构体`TreeNode`，包含一个整型变量`val`和两个指向左右子树的指针`left`和`right`。

2. 定义一个`Solution`类，其中包含一个`buildTree`函数，用于重建二叉树。该函数接受两个参数，分别是前序遍历序列`preorder`和中序遍历序列`inorder`，返回重建后的二叉树的根节点指针。

3. 在`buildTree`函数中，首先创建一个哈希表`inorder_map`，用于存储中序遍历序列中每个元素的值和下标的对应关系。

4. 调用`buildTreeHelper`函数，传入前序遍历序列、中序遍历序列、前序遍历序列的起始位置和结束位置、中序遍历序列的起始位置和结束位置以及中序遍历序列的哈希表。

5. 在`buildTreeHelper`函数中，首先判断前序遍历序列和中序遍历序列是否为空，如果是，则返回`NULL`。

6. 取出前序遍历序列的第一个元素作为根节点的值，创建一个新的`TreeNode`节点。

7. 在中序遍历序列中查找根节点的值，得到根节点在中序遍历序列中的下标`inorder_root_index`。

8. 计算左子树的大小`left_subtree_size`，即中序遍历序列中根节点左边的元素个数。

9. 递归调用`buildTreeHelper`函数，传入前序遍历序列、左子树的前序遍历序列的起始位置和结束位置、中序遍历序列、左子树的中序遍历序列的起始位置和结束位置以及中序遍历序列的哈希表，得到左子树的根节点指针，将其赋值给当前节点的左指针。

10. 递归调用`buildTreeHelper`函数，传入前序遍历序列、右子树的前序遍历序列的起始位置和结束位置、中序遍历序列、右子树的中序遍历序列的起始位置和结束位置以及中序遍历序列的哈希表，得到右子树的根节点指针，将其赋值给当前节点的右指针。

11. 返回当前节点的指针。