My C++ solution with O(n) time and O(lgn) space


  • 0
    M
    class Solution {
    public:
        void vector_cp(vector<int> in,vector<int> &out,int s,int t){
            for(int i=s;i<=t;i++)
            out.push_back(in[i]);
        }
        void Build(TreeNode* &root, vector<int>& inorder, vector<int>& postorder, int in_s, int in_t, int pos_s, int pos_t){
            int size=inorder.size();
            if(in_t<in_s)
            return;
            if(in_t==in_s){
                root=new TreeNode(inorder[in_s]);
                return;
            }
            int mid=postorder[pos_t];
            int idx;
            for(idx=in_t;idx>=in_s;idx--){
                if(inorder[idx]==mid)
                break;
            }
            root=new TreeNode(mid);
            Build(root->left,inorder,postorder,in_s,idx-1,pos_s,idx-in_s+pos_s-1);
            Build(root->right,inorder,postorder,idx+1,in_t,idx-in_s+pos_s,pos_t-1);
        }
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            TreeNode *rs=NULL;
            int size=inorder.size();
            Build(rs,inorder,postorder,0,size-1,0,size-1);
            return rs;
        }
    };
    

  • 0

    Recursion needs O(log n) space.


  • 0
    M

    @hwf Thank you for correction!


Log in to reply
 

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