剑指 Offer 07. 重建二叉树

题意

给出二叉树的前序和中序遍历，求二叉树

思路

在前序遍历中确定根节点，在中序遍历中确定左子树大小和右子树大小，并根据前序遍历确定左子树根节点和右子树根节点，递归即可得到最后结果

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int>preorder;
    unordered_map<int,int>mp;
    TreeNode* cur(int root,int left,int right){
        if(left>right) return nullptr;
        TreeNode* node = new TreeNode(preorder[root]);
        int i = mp[preorder[root]];
        node->left = cur(root+1,left,i-1);//递归左子树
        node->right = cur(root+i-left+1,i+1,right);//递归右子树
        //root表示当前根节点，左子树的大小 = (i-1-left+1),右子树的根节点=root+左子树大小+1
        return node;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;//this指针
        for(int i=0;i<inorder.size();i++){//建立哈希表，保存中序每个值的索引
            mp[inorder[i]]=i;
        }
        return cur(0,0,inorder.size()-1);//前序索引，中序索引，中序索引
    }
};