Recursive solution (24 MS) in C++


  • 0
    C
    unordered_map<int,int> map;
    TreeNode* solver(vector<int>& inorder, vector<int>& postorder, int sin, int ein, int spos, int epos){
        if(sin < 0 || sin>ein || ein>=inorder.size() || spos<0 || spos>epos || epos>=postorder.size())
            return NULL;
        if(sin == ein)
            return new TreeNode(inorder[sin]);
        int val = postorder[epos]; // last value of postorder array
        TreeNode* root = new TreeNode(val); // root value = last value
        int inpos = map[val]; // find position of root value in inorder array
        int l_sin = sin; int l_ein = inpos-1; // start and end for inorder array of left subtree
        int l_spos = spos; int l_epos = l_spos + (l_ein - l_sin); // start and end for postorder array of left subtree
        int r_sin = inpos+1; int r_ein = ein; // start and end for inorder array of right subtree
        int r_spos = epos - (r_ein - r_sin + 1); int r_epos = epos -1; // start and end for postorder array of right subtree
        root->left = solver(inorder,postorder,l_sin,l_ein,l_spos,l_epos); // build left subtree
        root->right = solver(inorder,postorder,r_sin,r_ein,r_spos,r_epos); // build right subtree
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int len = inorder.size()-1;
        for(int i=0;i<=len;i++)
            map[inorder[i]] = i;
        return solver(inorder,postorder,0,len,0,len);
    }

Log in to reply
 

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