C++ simple recursive solution


  • 100
    J
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, NULL, NULL);
    }
    
    bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
        if(!root) return true;
        if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
            return false;
        return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
    }

  • 0
    C

    Very concise solution.Can you tell me the time complexity of this solution?


  • 2
    J

    It is O(n). In worst case, we have to visit all the nodes in the tree.


  • 0
    Q

    the idea is do left-parent-right inorder traversal for left subtree, right-parent-left inorder traversal for right subtree, which might get better shortcircuit behavior in some cases, right?


  • 0
    J

    I don't get you question exactly. Main idea is just inorder traverse. The minimum and maximum values come from the parent node and if the value of current node is between minimum and maximum value, then visit left and right subtree for inorder traverse.


  • 9

    A more concise implementation:

    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            return help(root, LONG_MIN, LONG_MAX);
        }
        
        bool help(TreeNode* root, long min, long max){
            if(!root)   return true;
            if(root->val <= min || root->val >= max)  return false;
            return help(root->left, min, root->val) && help(root->right, root->val, max);
        }
    };

  • 0
    B

    A lot of the solutions are similar. Any one could instruct me why this one is particularly good?


  • 0
    L

    brilliant! How can you come up with this idea...


  • -1

    exactly it is preorder traverse


  • 0

    Absolutely brilliant solution


  • -1
    X

    @RainbowSecret I guess you do not know why you have to use LONG_MIN / LONG_MAX


  • 0
    S

    my straightforward without optimize:

    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            if(!root) return true;
            if(!root->left && !root->right) return true;
            if(root->left && !root->right) return isValidBST(root->left) && maxBST(root->left)<root->val;
            if(!root->left && root->right) return isValidBST(root->right) && minBST(root->right) > root->val;
            return isValidBST(root->left) && maxBST(root->left)<root->val && isValidBST(root->right) && minBST(root->right) > root->val;
    
        }
    private:
        int minBST(TreeNode* root) //assume it's a BST && root!=null
        {
            int min_val;
            while(root->left)
                root = root->left;
            min_val = root->val;
            return min_val;
        }
        int maxBST(TreeNode* root)
        {
            int max_val;
            while(root->right)
                root = root->right;
            max_val = root->val;
            return max_val;
        }
        
    };

  • 0
    F

    @sutongkui there are a lot of duplicate calculations in this method in the process of calculating the min or max value of
    a tree


Log in to reply
 

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