Largest BST Subtree
(Medium 333)
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.
Follow up:
Can you figure out ways to solve it with O(n) time complexity?
解题思路：bottom-up
其实可以用bottom-up的方法，根据左子树和右子树返回的信息就可以判断当前子树是不是BST。每个子树需要返回的信息有三个：
- 子树是不是BST
- MAX VALUE in this sub tree
- min value in this sub tree
private static int res = 0;
public static int largestBSTBetter(TreeNode root){
largestBSTHelper(root);
return res;
}
private static Data largestBSTHelper(TreeNode root){
Data curr = new Data();
if(root == null){
curr.isBST = true;
curr.size = 0;
return curr;
}
Data left = largestBSTHelper(root.left);
Data right = largestBSTHelper(root.right);
curr.min = Math.min(root.val, Math.min(right.min,left.min));
curr.max = Math.max(root.val, Math.max(right.max, left.max));
if(left.isBST && root.val > left.max && right.isBST && root.val < right.min){
curr.isBST = true;
curr.size = 1 + left.size + right.size;
if(curr.size > res)
res = curr.size;
}else{
curr.size = 0;
}
return curr;
}
}
class Data{
boolean isBST = false;
//the minimum for right sub tree or the maximum for right sub tree
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
//if the tree is BST, size is the size of the tree; otherwise zero
int size;
}