C++ solution using stack


  • 0
    M
    class Solution {
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            stack<TreeNode*> s;
            TreeNode* current = root;
            while(1){
                while(current){
                    s.push(current);
                    current = current->left;
                }
                if(s.empty())
                    break;
                TreeNode* node = s.top();
                s.pop();
                if(node->val == p->val){
                    current = node->right;
                    while(current){
                        s.push(current);
                        current = current->left;
                    }
                    if(!s.empty()){
                        TreeNode* result = s.top();
                        return result;
                    }
                    else    
                        return NULL;
    
                }
                else if(node->val > p->val){
                    return NULL;
                }
                else{
                    current = node->right;
                }
            }
            return NULL;
        }
    };

  • 0
    Y

    Simple Iterative C++ solution using stack

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            if(!root)
                return NULL;
            TreeNode* pt=root,*PREV=NULL;
            stack<TreeNode*> s;
            while(pt || !s.empty()){
                if(pt){
                    s.push(pt);
                    pt=pt->left;
                }
                else{
                    pt=s.top();
                    s.pop();
                    if(PREV==p)
                        return pt;
                    PREV=pt;
                    pt=pt->right;
                }
            }
            return NULL;
        }

Log in to reply
 

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