WEI-CHENG CHEN

說明

給後序跟中序，建立初二元樹

解法

class Solution {
public:
    TreeNode* f(map<int, int>& m, vector<int>& postorder, vector<int>& inorder,
        int postorder_left, // 後序遍歷起點索引
        int postorder_right, // 後序遍歷終點索引
        int inorder_left, // 中序遍歷起點索引
        int inorder_right // 中序遍歷終點索引
        ){
        // 結束條件：以後續去看
        if(postorder_left > postorder_right) return nullptr;
        int root_val = postorder[postorder_right]; // 後序的最後一個節點就是 root
        int root_index = m[postorder[postorder_right]]; // 查 root 在 inorder 的位置

        TreeNode* root = new TreeNode(root_val);
        int left_subtree = root_index - inorder_left;

        // 遞迴建立左子樹
        root->left = f(m, postorder, inorder,
                       postorder_left, postorder_left + left_subtree - 1,
                       inorder_left, root_index - 1);

        // 遞迴建立右子樹
        root->right = f(m, postorder, inorder,
                        postorder_left + left_subtree, postorder_right - 1,
                        root_index + 1, inorder_right);

        return root;
    }


    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        map<int, int> m;
        int n = inorder.size();
        for(int i=0;i<n;i++){
            m[inorder[i]] = i;
        }
        return f(m, postorder, inorder, 0, n-1, 0, n-1);
    }
};