My solution is right or not? (based on recursion)


  • 0
    R
       bool isValidBST(TreeNode *root){
        if (root == NULL || (root->left == NULL && root->right == NULL))
            return 1;                                             
        if (root->left != NULL){                                  
            if (root->left->val >= root->val)                     
                return 0;                                         
            else                                                  
                return 1 && isValidBST(root->left);
        }                         
        if (root->right != NULL){
            if (root->right->val <= root->val)
                return 0;
            else
                return 1 && isValidBST(root->right);
        }
        
    }
    

    Submission Result: Wrong Answer
    Input: {10,5,15,#,#,6,20}
    Output: true
    Expected: false


  • 0
    B

    Yes, your solution is wrong because it is basically checking that each individual node and its direct children fill the BST condition but that doesn't necessarily mean that each subtree holds the BST condition. In the Test example:

                   10
                  /    \ 
                5     15
               /   \   /   \
                      6   20
    

    Each node and its children fulfill the BST condition but as you can see '6' is less than '10'. so it should be on the left side.


Log in to reply
 

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