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

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

EX:

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

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

Ans:     3

           / \
         9  20
          /  \
       15   7

想法:

    我們知道給定一個 binary tree 的中序和後序/前序 排序就可以唯一決定一棵 binary tree，其中 後序/前序

排序可以決定當前子樹 root 的位置，而透過得知 root 後便可以在中序排序中找出該 root 的左右子樹包含的 node。

只要利用這個特性不斷往左右子樹進行搜索就可以建構出整個 binary tree。另外為了加快速度我們可以在一開始就

先建立中序排序中 node value 跟 index 的 mapping，這樣子一旦從後序排序得到 root 之後就可以直接從中序排序找到

root 的位置並確定左右子樹的 node。

完整程式碼:

解法一:

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

解法二(hashmap):

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