9ms c++ with 2 stacks


  • 0
    L
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            if(inorder.empty()){
                return NULL;
            }
            stack<int> root;
            stack<TreeNode *> children;
            size_t i = 0, j = 0;
            while(j != postorder.size()){
                if(!root.empty() && root.top() == postorder[j]){
                    root.pop();
                    TreeNode *p = new TreeNode(postorder[j]);
                    if(!children.empty()){
                        p->right = children.top();
                        children.pop();
                        if(!children.empty()){
                            p->left = children.top();
                            children.pop();
                        }
                    }
                    children.push(p);
                    ++j;
                }
                else if(postorder[j] == inorder[i]){
                    TreeNode *p = new TreeNode(postorder[j]);
                    if(!children.empty() && children.top()){
                        p->left = children.top();
                        children.pop();
                    }
                    else if(!children.empty() && !children.top()){
                        children.pop();
                    }
                    children.push(p);
                    ++j;
                    ++i;
                }
                else{
                    root.push(inorder[i]);
                    ++i;
                    if(!children.empty()){
                        children.push(NULL);
                    }
                }
            }
            return children.top();
        }
    };
    

Log in to reply
 

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