Largest BST in a Binary Tree

面接問題になると、面白いですね.
簡単な方法は、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.valprivate 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; }