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.
分析：http://www.cnblogs.com/grandyang/p/5188938.html
这道题让我们求一棵二分树的最大二分搜索子树，所谓二分搜索树就是满足左<根<右的二分树，我们需要返回这个二分搜索子树的节点个数。题目中给的提示说我们可以用之前那道Validate Binary Search Tree的方法来做，时间复杂度为O(nlogn)，这种方法是把每个节点都当做根节点，来验证其是否是二叉搜索数，并记录节点的个数，若是二叉搜索树，就更新最终结果，参见代码如下：
int largestBSTSubtree(TreeNode root) {
int[] res = new int[];
helper(root, res);
return res[];
}
void helper(TreeNode root, int[] res) { // assume eacho node is the root
if (root == null) return;
int d = count(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
res[] = Math.max(res[], d);
helper(root.left, res);
helper(root.right, res);
}
int count(TreeNode root, int mn, int mx) { // check whether it is a BST, if no, return -1, if yes, return its # of nodes.
if (root == null) return ;
if (root.val < mn || root.val > mx) return -;
int left = count(root.left, mn, root.val);
if (left == -) return -;
int right = count(root.right, root.val, mx);
if (right == -) return -;
return left + right + ;
}
O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int largestBSTSubtree(TreeNode root) {
int[] res = new int[];
largestBSTHelper(root, res);
return res[];
} private Data largestBSTHelper(TreeNode root, int[] res) {
Data curr = new Data();
if (root == null) {
curr.isBST = true;
curr.size = ;
return curr;
} Data left = largestBSTHelper(root.left, res);
Data right = largestBSTHelper(root.right, res);
if (left.isBST && root.val > left.max && right.isBST && root.val < right.min) {
curr.isBST = true;
curr.size = + left.size + right.size;
curr.min = Math.min(root.val, left.min);
curr.max = Math.max(root.val, right.max);
res[] = Math.max(res[], curr.size);
} else {
curr.size = ;
}
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;
}
http://blog.csdn.net/likecool21/article/details/44080779