重建二叉树详解

重点是哈希表的利用和左右子树的遍历区间确定

class Solution {
public:

map<int,int> hash;//创建一个哈希表
vector<int> preorder,inorder;
//因为要在中序遍历中快速找到某个值所在位置，所以利用哈希表来找，先预处理一下哈希表
    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
        preorder=_preorder,inorder=_inorder;
        for(int i=0;i<inorder.size();i++) hash[inorder[i]]=i;
        return dfs(0,preorder.size()-1,0,inorder.size()-1);//dfs就是输入前序遍历序列和中序遍历序列


    }
    TreeNode* dfs(int pl,int pr,int il,int ir){//返回值就是当前区间表示的子树的结点
        if(pl>pr) return nullptr;//如果当前子树为空直接返回空
        auto root=new TreeNode(preorder[pl]);//preorder[pl]前序遍历起始的数就是根节点
        int k=hash[root->val];//用哈希表快速找出根节点在中序遍历中的位置k
        auto left=dfs(pl+1,pl+k-il,il,k-1);//先遍历一下左子树的前序遍历和中序遍历，得到左子树的一个指针left
        //pl+1是因为pl位置是根节点，左子树应该是pl+1为起点，而长度应该是中序遍历左边的数数量，即为k-il，所以左子树
        //在前序遍历中的位置就是pl+1～pl+k-il；在中序遍历中的位置空间就是，il～k-1
        auto right=dfs(pl+k-il+1,pr,k+1,ir);
        //同理，右子树在前序遍历中的位置空间就是pl+k-il+1为起始位置，到pr；在中序遍历中的位置就是k+1到ir；
        root -> left=left,root->right=right;//将左子树和右子树插到当前根节点的位置上
        return root;
    }
};