C in 6 ms : no MIN/MAX, no in-order traversal


  • 0
    F

    May I provide an alternative C solution below?

    The main idea is to use recursion to carry out bottom-up validation. That is, to check from the leaves to the root.

    Suppose we have validated a node's left and right subtrees. What needs to be done to validate the whole tree?

    We only need to make sure the value of the node is between the value of the rightmost node in its left subtree and the value of the leftmost node in its right subtree.

    bool isValidBST(struct TreeNode *root)
    {
        if (root == NULL)
            return true;
        if (root->left != NULL && (!isValidBST(root->left) || rightmost(root->left) >= root->val))
            return false;
        if (root->right != NULL && (!isValidBST(root->right) || leftmost(root->right) <= root->val))
            return false;
        return true;
    }
    
    int leftmost(struct TreeNode *node)
    {   return (node->left == NULL) ? node->val : leftmost(node->left); }
    
    int rightmost(struct TreeNode *node)
    {   return (node->right == NULL) ? node->val : rightmost(node->right); }
    

Log in to reply
 

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