333. Largest BST Subtree

一刷

Each node is used exactly once, so Time O(n)
Space O(height)
99.86 %
class Solution {
    public int largestBSTSubtree(TreeNode root) {
        int[] max = new int[1];
        helper(root, max);
        return max[0];
    }
 
    // int[0] count -> -1, not valid bst
    // int[1] min
    // int[2] max
    private int[] helper(TreeNode node, int[] max) {
        int[] result = null;
        if (node == null) {
            result = new int[]{0};
            return result;
        }
        if (node.left == null && node.right == null) {
            result = new int[]{1, node.val, node.val};
        } else {
            int[] left = helper(node.left, max);
            int[] right = helper(node.right, max);
            if (left[0] == -1 || right[0] == -1
               || (left[0] != 0 && left[2] >= node.val)
               || (right[0] != 0 && right[1] <= node.val)) {
                    result = new int[]{-1};
             } else {
                result = new int[]{1, node.val, node.val};
                if (left[0] != 0) {
                    result[0] += left[0];
                    result[1] = left[1];
                }
                if (right[0] != 0) {
                    result[0] += right[0];
                    result[2] = right[2];
                }
            }
        }
        max[0] = Math.max(max[0], result[0]);
        return result;
    }
}