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.
一刷
题解:
如果root比左孩子要大是不够的,还要比左孩子的subtree的最小值要大。于是考虑创建一个object来保存。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
class Result{
int size;
int lower;
int upper;
// size of current tree, range of current tree [rangeLower, rangeUpper]
Result(int size, int lower, int upper){
this.size = size;
this.lower = lower;
this.upper = upper;
}
}
int max = 0;
public int largestBSTSubtree(TreeNode root) {
if(root == null) return 0;
traverse(root);
return max;
}
private Result traverse(TreeNode root){
if(root == null) return new Result(0, Integer.MAX_VALUE, Integer.MIN_VALUE);
Result left = traverse(root.left);
Result right = traverse(root.right);
if(left.size == -1 || right.size == -1 || root.val <= left.upper || root.val >= right.lower)
return new Result(-1, 0, 0);
int size = left.size + 1 + right.size;
max = Math.max(size, max);
return new Result(size, Math.min(left.lower, root.val), Math.max(right.upper, root.val));
}
}
二刷
题意是给一个binary tree, 问里面满足binary search tree的subtree的节点数目是多少。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class Subtree{
int lower;
int upper;
int size;
Subtree(int lower, int upper, int size){
this.lower = lower;
this.upper = upper;
this.size = size;
}
}
int max = 0;
public int largestBSTSubtree(TreeNode root) {
if(root == null) return 0;
traverse(root);
return max;
}
private Subtree traverse(TreeNode root){
if(root == null){
return new Subtree(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
}
Subtree left = traverse(root.left);
Subtree right = traverse(root.right);
int size = 0;
if(left.size!= -1 && right.size!=-1 && root.val > left.upper && root.val<right.lower) size = left.size + 1 + right.size;
else return new Subtree(0, 0, -1);
max = Math.max(size, max);
return new Subtree(Math.min(left.lower, root.val), Math.max(right.upper, root.val), size);//narrow the range
}
}