0333. Largest BST Subtree

https://leetcode.com/problems/largest-bst-subtree

Description

Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:

• The left subtree values are less than the value of their parent (root) node's value.

• The right subtree values are greater than the value of their parent (root) node's value.

Note: A subtree must include all of its descendants.

Follow up: Can you figure out ways to solve it with O(n) time complexity?

Example 1:

**Input:** root = [10,5,15,1,8,null,7]
**Output:** 3
**Explanation:** The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

Example 2:

**Input:** root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
**Output:** 2

Constraints:

• The number of nodes in the tree is in the range [0, 104].

• -104 <= Node.val <= 104

ac

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int maxSize = Integer.MIN_VALUE;

    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        valid(root);
        return maxSize;
    }

    public List<Integer> valid(TreeNode node) {

        List<Integer> res = new ArrayList<>();
        // exit
        if (node == null) {
            res.add(0);
            res.add(Integer.MAX_VALUE);
            res.add(Integer.MIN_VALUE);
            return res;
        }

        List<Integer> left = valid(node.left);
        List<Integer> right = valid(node.right);

        if (left == null || right == null) return null;
        if (left.get(2) < node.val && node.val < right.get(1)) {

            int size = left.get(0) + 1 + right.get(0);
            maxSize = Math.max(maxSize, size);
            res.add(size);
            int min = node.left == null ? node.val : left.get(1);
            int max = node.right == null ? node.val : right.get(2);
            res.add(min);
            res.add(max);
            return res;
        }

        return null;
    }
}

/*
Divide&Conquer. 1) return multiple information: size, min, max, if (left.get(2) < node.val && node.val < right.get(1)) we meet a valid BST, update information; 2) update max value on the fly;
*/