16 ms, c++, recursion solution share


  • 0
    T
    TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int pstart, int pend, int istart, int iend) {
        int pordersize = pend-pstart+1;
        if(pordersize == 0 || istart == -1) return NULL;
        if (pordersize == 1) return new TreeNode(preorder[pstart]);
        TreeNode* rtn = new TreeNode(preorder[pstart]);
        
        vector<int> pre_right, in_right, pre_left, in_left;
        
        int newprstart=-1, newprend = -1, newirstart = -1, newirend = -1, newplstart=-1, newplend = -1, newilstart = -1, newilend = -1;
        if(preorder[pstart] == inorder[istart]) {//left is null
            newprstart = pstart+1;
            newprend = pend;
            newirstart = istart+1;
            newirend = iend;
        }else if(preorder[pstart] == inorder[iend]){//right is null
            newplstart = pstart+1;
            newplend = pend;
            newilstart = istart;
            newilend = iend-1;
        }else {//none is null
            int rightpos = istart;
            while (rightpos < iend && preorder[pstart]!=inorder[rightpos]) rightpos++;
            
            newprstart = pstart+(rightpos-istart)+1;
            newprend = pend;
            newirstart = rightpos+1;
            newirend = iend;
            
            newplstart = pstart+1;
            newplend = pstart+(rightpos-istart);
            newilstart = istart;
            newilend = rightpos-1;
            
        }
        
        if(newprend!=-1) rtn->right = helper(preorder, inorder, newprstart, newprend, newirstart, newirend);
        if(newplend!=-1) rtn->left = helper(preorder, inorder, newplstart, newplend, newilstart, newilend);
        
        return rtn;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        
        
        return helper(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
        
    }

Log in to reply
 

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