95. Validate Binary Search Tree

Thinking

1.  因为递归，所以只要思考本身就行
2. 合理的二叉树 
1. root要比left subtree中的maximum大
2. root要比right subtree中的minimum小
3. left subtree 和 right subtree 都必须是合理的二叉树（这个第一次没有想到）

通过第二点合理的二叉树，可以依此建立一个class 作为返回类型

public class ReturnType {

int min;

int max;

boolean isBST;

public ReturnType (int min, int max, boolean isBST) {

this.min = min;

this.max = max;

this.isBST = isBST;

}

}

public ReturnType dfs(TreeNode root) {

        ReturnType ret = new ReturnType(Integer.MAX_VALUE, Integer.MIN_VALUE, true);

        

        if (root == null) {

            return ret;

        }

        

        ReturnType left = dfs(root.left);

        ReturnType right = dfs(root.right);

        

        if (!left.isBST || !right.isBST) {

            ret.isBST = false;

            return ret;

        }

        

        if(root.left != null && root.val <= left.max) {

            ret.isBST = false;

            return ret;

        }

        

         if(root.right != null && root.val >= right.min) {

            ret.isBST = false;

            return ret;

        }

        

        return new ReturnType(Math.min(root.val, left.min), Math.max(root.val, right.max), true);

        

        

    }