LeetCode - Validate Binary Search Tree

 Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public boolean isValidBST(TreeNode root) {

        if(root==null || (root.left==null && root.right==null)) {

            return true;

        }

        return check(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

    }

    

    public boolean check(TreeNode root, int min, int max) {

        if(root==null)  {

            return true;

        }

        return root.val>min && root.val<max && check(root.left, min, root.val) && check(root.right, root.val, max);

    }

}


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode *pre = NULL;
        return check(root, pre);
    }
 
    bool check(TreeNode* node, TreeNode* &pre) {
        if(node==NULL) {
            return true;
        }
        if(!check(node->left, pre)) {
            return false;
        }
        if(pre!=NULL && pre->val>=node->val) {
            return false;
        }
        pre = node;
        return check(node->right, pre);
    }
};/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
 
    private TreeNode pre = null;
 
    public boolean isValidBST(TreeNode root) {
        pre = null;
        return check(root);
    }
 
    public boolean check(TreeNode node) {
        if(node==null) {
            return true;
        }
        if(!check(node.left)) {
            return false;
        }
        if(pre!=null && pre.val>=node.val) {
            return false;
        }
        pre = node;
        return check(node.right);
    }
}


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode node) {
        if (node == null) {
            return true;
        }
        boolean isLeftOK = isValidBST(node.left);
        if (!isLeftOK) {
            return false;
        }
        if (lastVisit != null) {
            if (lastVisit.val >= node.val) {
                return false;
            }
        }
        lastVisit = node;
        boolean isRightOK = isValidBST(node.right);
        return isRightOK;
    }
 
    private TreeNode lastVisit = null;
 
}

===========

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   
    private TreeNode pre;
   
    public boolean isValidBST(TreeNode root) {
        pre = null;
        return visit(root);
    }
   
    private boolean visit(TreeNode node) {
        if (node == null) {
            return true;
        }
        if (!visit(node.left) || (pre != null && pre.val >= node.val)) {
            return false;
        }
        pre = node;
        return visit(node.right);
    }
}