105. Construct Binary Tree from Preorder and Inorder Traversal

題目網址：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

題意：給一 BT 的 preorder 和 inorder, 構建並返回該 BT。

tree 中沒有重複的元素。

Solution：

想法：利用 DFS, 跟 654. Maximum Binary Tree 類似, 只是可以先遍歷 inorder, 紀錄 inorder 元素的 idx, 讓後續遍歷 preorder 元素時可快速定位, 將時間複雜度降到 $O(n)$

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        cur = 0;
        // 紀錄 inorder 元素的 idx, 方便 preorder 快速定位
        for (int i = 0; i < inorder.size(); ++i) {
            index[inorder[i]] = i;
        }
        return dfs(preorder, 0, preorder.size() - 1);
    }

private:
    int cur; // preorder 當前要拜訪的 idx
    unordered_map<int, int> index; // {inorder[i], i}

    TreeNode* dfs(vector<int>& preorder, int left, int right){
        if (left > right) {
            return nullptr;
        }

        // 快速取得 preorder 元素在 inorder 中的 idx
        int idx = index[preorder[cur]];

        // 建立 root 後, cur 往下一個
        TreeNode *root = new TreeNode(preorder[cur++]);
        root->left = dfs(preorder, left, idx - 1);
        root->right = dfs(preorder, idx + 1, right);

        return root;
    }
};

• time：$O(n)$ ➔ 遍歷 preorder 和 inorder
• space：$O(n)$ ➔ 遞迴深度不超過 n