# 333 Largest BST Subtree

Input: root node of a binary tree

output: find the size of the largest subtree which is a Binary Search Tree (BST)

Concept:

程式分成三部分：

1. 主程式: 每圈要檢查root是否為null, 若left, right 都是null, return 1, 檢查root是不是合法BST(呼叫2), 如果是, 呼叫3, 算出root以下subtree的大小。recursive: 如果root不是valid，繼續檢查root下面的subtree，把自己的left child, right child丟進去跑，回傳Max(size(right),size(left))。
2. 判斷此root以下是否為合法BST: 若root是null, 合法。若root不符合上下界，不合法。recursive: 把left, right再丟進去檢查，若left, right都valid，這個root才是valid。
3. 計算此subtree的size: 若root是null，回傳0。若左右孩子都為null，回傳1。recursive: 將左右孩子丟進去跑，size(left)+size(right)+1即為此root的size

Pseudocode:

1. largestBSTSubtree input: TreeNode
   output: 最大subtree的size
   if(root==null) return 0;
   if(left == null && right == null) return 1;
   if(isValid(root)) countNode(root);
   return Max(largestBSTSubtree(right),largestBSTSubtree(left));

2. isValid
   input: TreeNode, min 下界, max 上界
   output: boolean
   if(root==null) return true;
   if(root.val <= min) return false;
   if(root.val >= max) return false;
   return isValid(right, root.val, max) && isValid(left, min, root.val)

3. countNode
   input: TreeNode
   output: size of this subtree
   if(root==null) return 0;
   if(left==null && right == null) return 1;
   return countNode(left)+countNode(right)+1;

完整程式碼:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
    public class Solution {
        public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (isValid(root, null, null)) return countNode(root);
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }

    public boolean isValid(TreeNode root, Integer min, Integer max) {
        if (root == null) return true;
        if (min != null && min >= root.val) return false;
        if (max != null && max <= root.val) return false;
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }

    public int countNode(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return 1 + countNode(root.left) + countNode(root.right);
    }
}