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

    }


}