105. Construct Binary Tree from Preorder and Inorder Traversal

解題思路

藉由 inorder 與 preorder 還原出原本的 binary tree 是資料結構中的內容，因此照著演算法模擬即可。

不過好像在時間複雜度上還有可進步的空間XD

程式碼

class Solution {
public:
    TreeNode* append(TreeNode* root, int value, unordered_map<int, int>& mp)
    {
        if(root == nullptr)
            root = new TreeNode(value);
        else if(mp[root->val] < mp[value])
            root->right = append(root->right, value, mp);
        else
            root->left = append(root->left, value, mp);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> mp;
        for(int i=0; i<inorder.size(); i++)
            mp[inorder[i]] = i;
        
        TreeNode* root = nullptr;
        for(int i=0; i<preorder.size(); i++)
            root = append(root, preorder[i], mp);
        return root;
    }
};