Two solutions of this question. In-order traverse and recursion by keep tracking bound.


  • 0
    X

    Solution 1:
    In-order traverse

    class Solution {
    public:
        bool InOrder(TreeNode* node, long& num){
            if(node==NULL)
                return true;
                
            bool r0=InOrder(node->left, num);
            bool r = node->val > num;
            num = node->val;
            bool r1=InOrder(node->right, num);
            
            return r0&&r&&r1;
        }
    
        bool isValidBST(TreeNode* root) {
            if(root==NULL)
                return true;
            long num=long(INT_MIN)*2;
            return InOrder(root, num);
        }
    };
    

    Solution 2:
    Recursively check whether the BST properties are kept in left and right subtrees. In the meantime, we need to keep tracking the low and high bound of each side.

     class Solution {
        public:
            bool helper(TreeNode* root, long lowBound, long highBound){
                if(root==NULL)
                    return true;
                
                bool left=root->left==NULL? true:(root->left->val < root->val) && (root->left->val > lowBound);
                bool right=root->right==NULL? true:( root->right->val > root->val) && (root->right->val < highBound);
                
                bool leftForest=helper(root->left, long(lowBound), min(long(highBound), long(root->val)));
                bool rightForest=helper(root->right, max(long(lowBound), long(root->val)), long(highBound));
                
                return left && right && leftForest && rightForest;
            }
            
            bool isValidBST(TreeNode* root) {
                if(root==NULL)
                    return true;
                return helper(root, long(INT_MIN)*2, long(INT_MAX)*2); // To tackle to corner case, multiply with 2.
            }
        };

Log in to reply
 

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