剑指 Offer 07. 重建二叉树

原题链接：剑指 Offer 07. 重建二叉树

 

soluition:

105. 从前序与中序遍历序列构造二叉树_anieoo的博客-CSDN博客

class Solution {
public:
    unordered_map<int,int> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0;i < inorder.size();i++)
            pos[inorder[i]] = i;    //记录每个节点在中序数组中的位置
        return Build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

    TreeNode *Build(vector<int> &pre, int p_l, int p_r, vector<int> &ino, int in_l, int in_r) {
        if(p_l > p_r) return nullptr;

        int k = pos[pre[p_l]] - in_l;
        TreeNode *root = new TreeNode(pre[p_l]);
        root->left = Build(pre, p_l + 1, p_l + k, ino, in_l, in_l + k - 1);
        root->right = Build(pre, p_l + k + 1, p_r, ino, in_l + k + 1, in_r);
        return root;
    }
};