验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

1 2	输入：root = [2,1,3] 输出：true

思路：判断二叉搜索树合法，需要根节点判断左右子树最大最小节点满足题目关系。可以维护一个子节点值范围（递归子节点时维护并判断当前节点合法性），通过此范围与根节点值判断。从而判断该节点是否合法。

递归思路：先自顶向下分析，然后分析底层边界逻辑反向验证，然后开始实现。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        Integer[] vals = new Integer[2];
        return isValid(root, vals);
    }

    /**
     * root：要判断合法的子树根节点
     * vals：该子树值范围
     *
     */
    public boolean isValid(TreeNode root, Integer[] vals) {
        if(root == null) { 
            return true;
        }
        // 对于叶子节点还是其他都出实话当前值作为范围
        vals[0] = root.val;
        vals[1] = root.val;

        if(root.left != null) {
            // 此处用一个新的对象，防止污染当前节点范围
            Integer[] tval = new Integer[2];
            boolean left = isValid(root.left, tval);
            if(!left) {
                return false;
            }
            if(root.val <= tval[1]) {
                return false;
            }
            if(tval[1] >= root.val){
                return false;
            }
            // 以左子树范围更新当前节点范围，如果上面条件通过则树合法，以子树范围更新可以扩大当前子树值范围
            vals[0] = tval[0];
        }
        // 同上
        if(root.right != null){
            Integer[] tval = new Integer[2];
            boolean right = isValid(root.right, tval);
            if(!right) {
                return false;
            }
            if(root.val >= tval[0]) {
                return false;
            }
            if(tval[0] <= root.val){
                return false;
            }
            vals[1] = tval[1];
        }
        return true;
    }
}