Concise c++ solution (17 lines)


  • 0
    L
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            if (inorder.empty() || postorder.empty()) return nullptr;
            unordered_map<int, int> umap;
            for (int i = 0; i < inorder.size(); ++i) umap[inorder[i]] = i;
            return buildCore(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, umap);
        }
        
        TreeNode* buildCore(vector<int>& inorder, int il, int ir, vector<int>& postorder, int pl, int pr, unordered_map<int, int>& umap) {
            if (pl > pr || il > ir) return nullptr;
            TreeNode* root = new TreeNode(postorder[pr]);
            int i = umap[postorder[pr]];
            root->left = buildCore(inorder, il, i - 1, postorder, pl, pl + i - il - 1, umap);
            root->right = buildCore(inorder, i + 1, ir, postorder, pl + i - il, pr - 1, umap);        
            return root;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.