Memory Limit Exceeded


  • 0
    K
    class Solution {
    public:
        TreeNode *buildTree(vector<int> &inorder, vector<int> &preorder) {
            if (inorder.size() == 0) return nullptr;
            stack<TreeNode*> s;
            int initer = 0, preiter = 0;
            TreeNode *root = new TreeNode(preorder[preiter++]);
            TreeNode *p = nullptr;
            s.push(root);
            while (true) {
                // The node on top of the stack has no left sub-tree
                if (s.top()->val == inorder[initer]) {
                    p = s.top();
                    s.pop();
                    ++initer;
                    if (initer == inorder.size()) break;
                    if (s.size() && s.top()->val == inorder[initer]) continue;
                    p->right = new TreeNode(preorder[preiter++]);
                    s.push(p->right);
                } else {    
                    p = new TreeNode(preorder[preiter++]);
                    s.top()->left = p;
                    s.push(p);
                }
            }
            return root;
        }   
    };
    

    I solve this problem by using stack and maintain the root of each subtree iteratively. But the OJ says my program gets Memory Limit Exceeded, no idea why. This algorithm has time and space complexity O(n). Could anyone help me on this?


Log in to reply
 

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