C++ easy to read in-order traversal solution


  • 16
    P

    Ensure that every next node of in-order traversal is larger than previous one. Using boolean flag to start with the left most node.

    class Solution {
        bool first = true;
        int prev = 0;
    public:
        bool isValidBST(TreeNode *root) {
            if(root == NULL) return true;
            
            return (
                isValidBST(root->left)
                && check(root->val)
                && isValidBST(root->right));
        }
        
        bool check(int val)
        {
            if(first)
            {
                first = false;
                prev = val;
                return true;
            }
            
            if(prev >= val) return false;
            
            prev = val;
            return true;
        }
    };

  • 0
    A
    This post is deleted!

  • 4

    A more concise solution

    class Solution {
    private:
        TreeNode* prev=NULL;
    public:
        bool isValidBST(TreeNode* root) {
            if(!root)   return true;
            return isValidBST(root->left)  && help(root) && isValidBST(root->right);
        }
        
        bool help(TreeNode* root){
            if(!prev){
                prev=root;
                return true;
            }
            if(prev->val >= root->val)   return false;
            prev=root;
            return true;
        }
    };

Log in to reply
 

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