98. Validate Binary Search Tree Leetcode Java

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.

Solution:

1. In order traversal

A valid BST will have a well-ordered in order traversal, predecessor.val < cur.val < successor.val. So we need to maintain a pre variable to store the predecessor, each time when we "output" the current treenode compare the value with the pre.val, if pre.val>=cur.val, return false. If we can finish the in order traversal, which means all nodes are well ordered, we can say it is a valid BST.
I use the morris Algorithm to do the in order traversal.

 public boolean isValidBST(TreeNode root) {  
    if(root==null) return true;  
    TreeNode pre=null;  
    while(root!=null){  
      if(root.left==null){  
       if(pre!=null && pre.val>=root.val) return false;  
       pre=root;  
       root=root.right;  
      }  
      else {  
        TreeNode l=root.left;  
        while(l.right!=null && l.right!=root) l=l.right;  
        if(l.right==null){  
          l.right=root;  
          root=root.left;  
        }  
        else{  
         if(pre!=null && pre.val>=root.val) return false;  
          pre=root;  
          root=root.right;  
          l.right=null;  
        }  
      }  
    }  
    return true;  
   }  

1. Squeeze the Min and Max
If we have negative infinite and positive infinite, the root must be between this range, while root.left must between negative infinite and root.val, and root.right must between root.val and positive infinite. We can keep traversing next level and squeezing the ranging, if any node is not in the range return false, otherwise, return the check result of its left child with the squeezed range && the check result of it right child. 
Since we use the Integer.MIN_VALUE and MAX_VALUE as the negative and positive infinity, we have to take care of these two special cases. 

  public boolean isValidBST(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;  
     if(root.val==Integer.MIN_VALUE){  
       if(root.left!=null) return false;  
       return helper(root.right,root.val+1,max);  
     }  
     else if(root.val==Integer.MAX_VALUE){  
       if(root.right!=null) return false;  
       return helper(root.left,min,root.val-1);  
     }  
     else return helper(root.left, min, root.val-1) && helper(root.right, root.val+1,max);  
   }