333.最大BST子树

333.最大BST子树

题目： 给定一个二叉树，找到其中最大的二叉搜索树(BST)子树，其中最大指的是子树节点最多的；
注意：子树必须包含其所有后代

示例 ：输入：[10,5,15,1,8,null,7]

            10
           /     \
       5      15
   /   \          \
1   8       7

输出：3 解释：1 5 8 是 BST 子树

思路一： 自顶向下 前序遍历
先以根结点遍历判断是否是BST, 再以根结点的左子树为根节点判断是否是BST, 以此类推 遍历完左边 就遍历右边子树;
如此前序遍历时间复杂度是O(n) ，判断一颗树是否为BST的时间复杂度是O(n) 相乘总时间复杂度是O(n^2)
由于是自顶向下的遍历方式，所以在判断一棵树是否为BST方面,存在重复遍历判断的情况

思路二： 自底向上 后序遍历 , 此方法优于思路一

以一个结点为根节点，先确定左子树和右子树是否是BST ，然后再推断出加上根节点后是否是BST; 以此类推得到最大的BST

class Solution {
  
  //定义结构BST 根节点信息
  private static class Info {
      /** 根节点*/
      public TreeNode root;
      /** 节点数*/
      public int size;
      /** 最大节点*/
      public int max;
      /** 最小节点*/
      public int min;
      
      public Info(TreeNode root,int size,int max,int min) {
          this.root = root;
          this.size = size;
          this.max = max;
          this.min = min;
      }
  }

  //最大BST子树
  public int largestBSTSubtree(TreeNode root) {
      return (root==null)?0:getInfo(root).size;
  }

  /** 返回以root为根节点的二叉树的最大BST子树的信息 */
  private Info getInfo(TreeNode root) {

      if(root == null) return null;

      //li(left info) 左子树最大BST信息
      Info li = getInfo(root.left);
            
      //ri(right info) 右子树最大BST信息
      Info ri = getInfo(root.right);

      //1. 以root为根节点的二叉树就是BST
      /** 

       整棵都是BST 有4种情况
       1. 左右子树都为空，只剩一个根节点，单节点树必然是BST; 
       代码表示: li==null && ri==null

       2. 只有左子树 && 左子树整个是BST && 左子树最大节点的val小于root的val 结论 那么加上根节点依然是BST 
       代码表示: li != null && ri == null && li.root == root.left && li.max < root.val

       3. 只有右子树&& 右子树整个是BST && 右子树最小节点的val大于root的val 结论 那么加上根节点依然是BST
       代码表示: ri != null && li == null && ri.root == root.right && ri.min > root.val

       4. 左子树整棵都是BST && 右子树整棵都是BST && 左子树的最大节点的val小于root的val && 右子树的最小节点的val大于root的val
       li != null && ri != null && 
       li.root == root.left && li.max < root.val &&
       ri.root == root.right && ri.min > rootroot.val

       */
       
       //定义左子树BST节点数 ，初始为-1是  因为左右子树BST的size是大于等于0的 这样方便判断左右子树是否为空
       int leftBSTSize = -1;
       int rightBSTSize = -1;

       //假设最大值最小值都有可能是根节点的本身，左边是空最小值是本身、右边是空的最大值是本身、或左右都为空 最大最小都是本身
       int max = root.val;
       int min = root.val;

       //解释：左子树和右子树的情况组合 就是上面分析的四种情况

       //左子树的情况
       if(li==null) {
           leftBSTSize = 0;
       }else if(li.root==root.left && li.max < root.val) {
          leftBSTSize = li.size;
          //左边不为空且是完整BST,修改最小值
          min = li.min;
       }

       //右子树的情况
       if(ri==null) {
          rightBSTSize = 0;
       }else if(ri.root == root.right && ri.min > root.val) {
          rightBSTSize = ri.size;
          //右边不为空且是完整BST,修改最大值
          max = ri.max;
       }
       
       //以root为根节点的二叉树就是BST
       if(leftBSTSize>=0 && rightBSTSize>= 0) {
           return new Info(root, 1 + leftBSTSize + rightBSTSize,max,min);
       }

      //2. 以root为根节点的二叉树不是BST 

      //2.1 左右子树都不为空，那就返回BST子树节点较多的那个
      if(li != null && ri != null) return (li.size > ri.size) ? li:ri;

      //2.2 只有左子树范围内或右子树范围内有BST 且 另一边必然是null
      /**
       能来到这里就说明：左子树整树 或 右子树整树 肯定都不是BST，那就只剩下 左边有BST 和 右边有BST 这两种情况  
       li 就是 左子树最大BST信息
       ri 就是 右子树最大BST信息
       所以就有了下面的代码
       */
      return (li == null)?ri:li;

  }

}