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:
A subtree must include all of its descendants.
Here's an example:
10 / \ 5 15 / \ \ 1 8 7The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree's size, which is 3.
Code:
public int largestBSTSubtree(TreeNode root) {
if (isValid(root,Integer.MAX_VALUE,Integer.MIN_VALUE)){
return count(root);
}
return Math.max(largestBSTSubtree(root.left),largestBSTSubtree(root.right));
}
private boolean isValid(TreeNode root,int max,int min){
if (root == null) return true;
if (root.val > min && root.val < max){
return isValid(root.left,root.val,min) && isValid(root.right,max,root.val);
}
return false;
}
private int count(TreeNode root){
if (root == null) return 0;
return 1 + count(root.left) + count(root.right);
}
No comments:
Post a Comment