333. Largest BST Subtree

T: O(n)
S: O(1)

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    private record Result(int min, int max, int count){};
    public int largestBSTSubtree(TreeNode root) {
        int[] result = new int[1];
        dfs(root, result);
        return result[0];
    }
    private Result dfs(TreeNode node, int[] result) {
        if (node == null) {
            return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }
        Result left = dfs(node.left, result);
        Result right = dfs(node.right, result);
        if (left != null && right != null) {
            if (node.val > left.max && node.val < right.min) {
                int total = left.count + right.count + 1;
                int max = Math.max(right.max, node.val);
                int min = Math.min(left.min, node.val);
                result[0] = Math.max(result[0], total); // notice: find the max one subtree size

                return new Result(min, max, total);
            }
        }

        return null;
    }
}

/***
how to know its a BST?

node.val > left tree larget number
node.val < right tree smallest number

so try to keep the left tree larget number and right tree smallest number
and maitain a "max" subBST size! (because every dfs's count result is different!)

T: O(n)
S: O(1)
 */