LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal [Medium] [C++] 解題筆記

這題給我們一個 binary tree 的中序和前序排序，要我們反推出整個 tree 的結構，其中 tree 的每個node 皆不重複。

EX:

        preorder = [3,9,20,15,7]

        inorder = [9,3,15,20,7]

                3
               / \
  Ans:    9  20
              /  \
           15   7

想法:

    這題基本上和 106. Construct Binary Tree from Inorder and Postorder Traversal 一模一樣，

只差在 root 在前序排序中會是第一個 node 而已，因此只需要小心 recursive 建樹時的 index 設定即可。

完整程式碼:

class Solution {
public:
    unordered_map<int, int> m;
    TreeNode* constructBT(vector<int>& preorder, int p_left, int p_right, vector<int>& inorder, int i_left, int i_right) {
        if (p_left > p_right || i_left > i_right) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[p_left]);
        int root_pos = m[root->val];
        root->left = constructBT(preorder, p_left + 1, p_right - (i_right - root_pos), inorder, i_left, root_pos - 1);
        root->right = constructBT(preorder, p_left + 1 + (root_pos - i_left), p_right, inorder, root_pos + 1, i_right);
                                  
        return root;                    
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            m[inorder[i]] = i;
        }
        return constructBT(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
};