C++ 10 lines iterative solution using stack.


  • 0
    J
    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            vector<TreeNode*> S;
            TreeNode* n = root, *last_n = NULL;
            while(true){
                while(n) { S.push_back(n); n = n->left;}   // push subtree of n into stack
                if(S.empty()) return true;  
                if(last_n && (S.back())->val <= last_n->val) return false; // check
                last_n = S.back();   // prepare for next loop
                S.pop_back();
                n = n->right;
            }
        }
    };
    

Log in to reply
 

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