Leetcode: 333. Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here's an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one. 
The return value is the subtree's size, which is 3.

Hint:

1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

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

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

/**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ public class Solution {     private int max = 0;     public int largestBSTSubtree(TreeNode root) {         if (root == null) {             return 0;         }                   largestBSTHelper(root);                   return max;     }           private Data largestBSTHelper(TreeNode root) {         Data curr = new Data();         if (root == null) {             curr.isBST = true;             return curr;         }                   Data left = largestBSTHelper(root.left);         Data right = largestBSTHelper(root.right);                   curr.lower = Math.min(root.val, Math.min(left.lower, right.lower));         curr.upper = Math.max(root.val, Math.max(left.upper, right.upper));                   if (left.isBST && root.val > left.upper && right.isBST && root.val < right.lower) {             curr.size = left.size + right.size + 1;             curr.isBST = true;             max = Math.max(max, curr.size);         } else {             curr.size = 0;         }                   return curr;     } }   class Data {     int size = 0;     int lower = Integer.MAX_VALUE;     int upper = Integer.MIN_VALUE;     boolean isBST = false; }