Largest BST in a Binary Tree
面接問題になると、面白いですね.
簡単な方法は、nodeごとにisBSTのテストを行い、最大のものを見つけることです.
上の方法はtop-downのアクセスですが、実はbottom-upの方法で、左サブツリーと右サブツリーが返す情報から現在のサブツリーがBSTかどうかを判断することができます.各サブツリーに返される情報は3つあります.
1.サブツリーはBSTか
2.MAX VALUE in this sub tree
3.min value in this sub tree
まず左右のサブツリーの結果を再帰的に得,次に現在のnode.val>left.max&&node.val
簡単な方法は、nodeごとにisBSTのテストを行い、最大のものを見つけることです.
public static int largestBSTNaive(TreeNode root){
if(isBST(root)){
return size(root);
}
return Math.max(largestBSTNaive(root.left), largestBSTNaive(root.right));
}
private static int size(TreeNode root) {
if(root == null)
return 0;
return 1 + size(root.left) + size(root.right);
}
private static boolean isBST(TreeNode root) {
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private static boolean isBST(TreeNode root, int min, int max) {
if(root == null)
return true;
if(root.val >= max)
return false;
else if(root.val <= min)
return false;
return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
}上の方法はtop-downのアクセスですが、実はbottom-upの方法で、左サブツリーと右サブツリーが返す情報から現在のサブツリーがBSTかどうかを判断することができます.各サブツリーに返される情報は3つあります.
1.サブツリーはBSTか
2.MAX VALUE in this sub tree
3.min value in this sub tree
まず左右のサブツリーの結果を再帰的に得,次に現在のnode.val>left.max&&node.val
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;
}