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.

Analysis

1. 容易写错的方法：左右都是valid bst, 且当且left值小于root，right值大于root，并不能保证就是valid BST，例子:

    10
    /\
   5 15
     /\
    6 20
   

2. 注意一开始要pass null，不能pass Integer.MAX_VALUE和Integer.MIN_VALUE。例子：root.val为Integer.MAX_VALUE或Integer.MIN_VALUE时出错。

3. 注意helper function的parameter是Integer，not int。Int不能take null as value.

Code

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root, null, null);
    }

    private boolean valid(TreeNode root, Integer min, Integer max){
        if (root==null) return true;
        return (min==null || root.val>min) && (max==null || root.val<max) && valid(root.left, min, root.val) && valid(root.right, root.val, max);
    }
}