C++ solution beats 82% of the submission 20 ms


  • 0

    C++ solution beats 82% of the submission 20 ms

    Here is the solution, which does recursion and also uses
    hash map to store the indexes of the inorder array.
    This optimizes the search of elements.

    TreeNode* buildTreeUtil(vector<int>& preorder, int preS, int preE, vector<int>& inorder, int inS, int inE, unordered_map<int, int>& hmap) {
    if(preS > preE || inS > inE)
    return nullptr;

        TreeNode* root;     
        if(preS == preE) {
            root = new TreeNode(preorder[preS]);
            return root;
        }    
        int idx = hmap[preorder[preS]];
    
        root = new TreeNode(preorder[preS]);
        
        root->left = buildTreeUtil(preorder, preS+1, preS+idx-inS, inorder, inS, idx-1, hmap);
        root->right = buildTreeUtil(preorder, preS+idx-inS+1, preE, inorder, idx+1, inE, hmap);
        return root;
    }
    
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() != inorder.size())
            return nullptr;
        
        unordered_map<int, int> hmap;
        
        for(int i=0; i<inorder.size(); i++)
            hmap[inorder[i]] = i;
            
        return buildTreeUtil(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1, hmap);    
    }

Log in to reply
 

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