98.Validate Binary Search Tree(M)

1.Description(Medium)

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.

• A single node tree is a BST

Example

An example:

  2
 / \
1   4
   / \
  3   5

The above binary tree is serialized as{2,1,4,#,#,3,5}(in level order).

2.Code

Version 1:

根据题目中的定义来实现，其实就是对于每个结点保存左右界，也就是保证结点满足它的左子树的每个结点比当前结点值小， 右子树的每个结点比当前结点值大。对于根节点不用定位界，所以是无穷小到无穷大，接下来当我们往左边走时，上界就变成当前结点的值，下界不变，而往右边走时，下界则变成当前结点值，上界不变。 如果在递归中遇到结点值超越了自己的上下界，则返回false，否则返回左右子树的结果

public boolean isValidBST1(TreeNode root){
         return helper(root,Integer.MIN_VALUE,Integer.MAX_VALUE);

     }
     public boolean helper(TreeNode root,int min,int max){
         if(root==null){
             return true;
         }

        if(root.val>=max || root.val<=min){
            return false;
        }
        return helper(root.left,min,root.val)&& helper(root.right,root.val,max);
     }

*放在Lintcode中跑不过是因为testcase 中就一个根结点而且根结点超过Integer.MAX_VALUE

testcase:[2147483647]

对于这种情况， 可以改成以下代码可以避免：

boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    // base case
    if (root == null) return true;
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (min != null && root.val <= min.val) return false;
    if (max != null && root.val >= max.val) return false;
    // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
    return isValidBST(root.left, min, root) 
        && isValidBST(root.right, root, max);
}

Version 2: In order traverse (use a static variable to store the previous value)

1. 对一个BST进行inorder traverse，必然会得到一个严格单调递增序列，否则则是invalid BST。

2. Inorder traverse时并不需要记录下整个访问过的序列，而只需要保存前一个访问的节点数值就可以了。

这个做法不会过只有一个元素而且这个元素比Integer.MIN_VALUE还小的值。

testcase:[-2147483648]

    public static int previous=Integer.MIN_VALUE;
    public boolean isValidBST2(TreeNode root){

        if(root==null){
            return true;
        }
        //the left tree
        if(isValidBST2(root.left)==false){
            return false;
        }

        //the current node
        if(root.val<=previous){
            return false;
        }
        previous=root.val;

        //the right tree
        if(isValidBST2(root.right)==false){
            return false;
        }

        return true;
    }

改进：

加一个firstNode的判断，一开始是true, 第一次运行后立刻改成false

    public int previous=Integer.MIN_VALUE;
    public boolean firstNode=true;

    public boolean isValidBST(TreeNode root) {

       if(root==null){
           return true;
       }
       //left tree:
       if(isValidBST(root.left)==false){
           return false;
       }

       //current node
       if(!firstNode && root.val<=previous){
           return false;
       }
       firstNode=false;
       previous=root.val;

       //right tree
       if(isValidBST(root.right)==false){
           return false;
       }

       return true;
    }