C++ stack soln, double pointers 32ms


  • 0
    K
        TreeNode* deleteNode(TreeNode* root, int key) {
            if(!root) return nullptr;
            stack<TreeNode**> sk;
            sk.push(&root);
            while(!sk.empty()) {
                auto dbcurr = sk.top();
                auto curr = *sk.top();
                sk.pop();
                if(curr->val < key) { if(curr->right) sk.push(&(curr->right)); }
                else if(curr->val > key) { if(curr->left) sk.push(&(curr->left)); }
                else {
                    auto l = curr->left, r = curr->right;
                    delete curr;
                    if(!l) *dbcurr = r;
                    else {
                        *dbcurr = l;
                        auto it = l;
                        while(it->right) it = it->right;
                        it->right = r;
                    }
                    break;
                }
            }
            return root;
        }
    

Log in to reply
 

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