My 12ms C++ solution


  • 0
    L

    Refer to the following solution to the No. 105
    https://leetcode.com/discuss/28271/my-o-n-19ms-solution-without-recusion-hope-help-you

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.size() == 0) return NULL;
        int n = postorder.size();
        TreeNode* root = new TreeNode(postorder[n - 1]);
        stack<TreeNode*> myStack;
        myStack.push(root);
        int index = n - 1;
        for(int i = n - 2; i >= 0; i--){
            TreeNode* cur = myStack.top();
            if(myStack.top() -> val != inorder[index]){
                cur -> right = new TreeNode(postorder[i]);
                myStack.push(cur -> right);
            }
            else{
                while(!myStack.empty() && myStack.top() -> val == inorder[index]){
                    cur = myStack.top();
                    myStack.pop();
                    index--;
                }
                if(index >= 0){
                    cur -> left = new TreeNode(postorder[i]);
                    myStack.push(cur -> left);
                }
            }
        }
        return root;
    }

Log in to reply
 

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