12ms c++ solution with recursion, beating 97% others.


  • 0
    S
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            if(postorder.size() == 0) return nullptr;
            return helper(inorder,postorder,0,inorder.size()-1, 0, postorder.size()-1);
        }
    private:
        TreeNode* helper(vector<int>& inorder, vector<int>& postorder, int is, int ie, int ps, int pe){
            if(ps > pe) return nullptr;
            int v = postorder[pe];
            TreeNode* root = new TreeNode(v);
            if(ps == pe) return root;
            int i = ie, num = 0;
            while(i >= 0 && inorder[i] != v){
                i--;
                num++;
            }
            root->left = helper(inorder,postorder,is,i-1,ps,pe-num-1);
            root->right = helper(inorder,postorder,i+1,ie,pe-num,pe-1);
            
            return root;
        }
    };

Log in to reply
 

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