package com.binaryTree;

// 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
//有效 二叉搜索树定义如下:
//节点的左子树只包含 小于 当前节点的数。
//节点的右子树只包含 大于 当前节点的数。
//所有左子树和右子树自身必须也是二叉搜索树。
//链接:https://leetcode-cn.com/problems/validate-binary-search-tree
public class IsValidBST {

 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;
 }
 }

 public static class Info{
 public int max;
 public int min;
 public boolean isValid;

 public Info(int max, int min, boolean isValid) {
 this.max = max;
 this.min = min;
 this.isValid = isValid;
 }
 }

 public static boolean isValidBST(TreeNode root) {
 if (root == null) return true;

 return process(root).isValid;
 }

 public static Info process(TreeNode node){
 if (node == null) return null;

 Info leftInfo = process(node.left);
 Info rightInfo = process(node.right);

 int max = node.val;
 int min = node.val;
 if (leftInfo != null){
 max = Math.max(max,leftInfo.max);
 min = Math.min(min,leftInfo.min);
 }
 if (rightInfo != null){
 max = Math.max(max,rightInfo.max);
 min = Math.min(min,rightInfo.min);
 }
 boolean isValid = true;
 // 注意,左右子树是否为有效二叉搜索树的条件是:左右子树不为空+左右子树是否有效
 if (leftInfo != null && !leftInfo.isValid){
 isValid = false;
 }
 if (rightInfo != null && !rightInfo.isValid){
 isValid = false;
 }
 // 注意:这里将node.val与左右子树的节点值进行比较时,需要是符合 二叉搜索树的相反条件
 if (leftInfo != null && node.val <= leftInfo.max){
 isValid = false;
 }

 if (rightInfo != null && node.val >= rightInfo.min){
 isValid = false;
 }
 return new Info(max,min,isValid);

 }


}