22ms C++ solution - O(n^2)


  • 1
    S
    TreeNode* getRoot(vector<int>& in, int l1, int r1, vector<int>& pre, int l2, int r2){
            if(l1>r1 || l2>r2){
                return NULL;
            }
            TreeNode* root = new TreeNode(pre[l2]);
            if(l1==r1){
                return root;
            }
            int val = root->val;
            int i=l1;
            for(i=l1;i<=r1;i++){
                if(in[i]==val){
                    break;
                }
            }
            i--;
            root->left=getRoot(in,l1,i,pre,l2+1,l2+(i-l1+1));
            root->right=getRoot(in,i+2,r1,pre,r2-(r1-i-2),r2);
            return root;
        }
        TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
            //post[post.size()-1] : root
            if(pre.size()==0){
                return NULL;
            }
            return getRoot(in,0,in.size()-1,pre,0,pre.size()-1);
        }
    

Log in to reply
 

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