Minimum Subtree
Subtree with Maximum Average
Largest BST Subtree
For this kind of question, we have a create a ResultType class to help us deal with multiple return value situation, this approach can reduce or avoid global variable.
Minimum Subtree: http://www.lintcode.com/en/problem/minimum-subtree/
// version 1 : traverse + divide conquer
public class Solution {
private TreeNode subtree = null;
private int subtreeSum = Integer.MAX_VALUE;
/**
* @param root the root of binary tree
* @return the root of the minimum subtree
*/
public TreeNode findSubtree(TreeNode root) {
helper(root);
return subtree;
}
private int helper(TreeNode root) {
if (root == null) {
return 0;
}
int sum = helper(root.left) + helper(root.right) + root.val;
if (sum <= subtreeSum) {
subtreeSum = sum;
subtree = root;
}
return sum;
}
}
// version 2: Pure divide conquer
class ResultType {
public TreeNode minSubtree;
public int sum, minSum;
public ResultType(TreeNode minSubtree, int minSum, int sum) {
this.minSubtree = minSubtree;
this.minSum = minSum;
this.sum = sum;
}
}
public class Solution {
/**
* @param root the root of binary tree
* @return the root of the minimum subtree
*/
public TreeNode findSubtree(TreeNode root) {
ResultType result = helper(root);
return result.minSubtree;
}
public ResultType helper(TreeNode node) {
if (node == null) {
return new ResultType(null, Integer.MAX_VALUE, 0);
}
ResultType leftResult = helper(node.left);
ResultType rightResult = helper(node.right);
ResultType result = new ResultType(
node,
leftResult.sum + rightResult.sum + node.val,
leftResult.sum + rightResult.sum + node.val
);
if (leftResult.minSum <= result.minSum) {
result.minSum = leftResult.minSum;
result.minSubtree = leftResult.minSubtree;
}
if (rightResult.minSum <= result.minSum) {
result.minSum = rightResult.minSum;
result.minSubtree = rightResult.minSubtree;
}
return result;
}
}
Subtree with Maximum Average: http://lintcode.com/en/problem/subtree-with-maximum-average/#
// version 1: Traverse + Divide Conquer
public class Solution {
private class ResultType {
public int sum, size;
public ResultType(int sum, int size) {
this.sum = sum;
this.size = size;
}
}
private TreeNode subtree = null;
private ResultType subtreeResult = null;
/**
* @param root the root of binary tree
* @return the root of the maximum average of subtree
*/
public TreeNode findSubtree2(TreeNode root) {
helper(root);
return subtree;
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(0, 0);
}
ResultType left = helper(root.left);
ResultType right = helper(root.right);
ResultType result = new ResultType(
left.sum + right.sum + root.val,
left.size + right.size + 1
);
if (subtree == null ||
subtreeResult.sum * result.size < result.sum * subtreeResult.size
) {
subtree = root;
subtreeResult = result;
}
return result;
}
}
Largest BST Subtree: https://leetcode.com/problems/largest-bst-subtree/#/description
/**
* 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 num;
int min;
int max;
boolean isBST;
public Result(int num, int min, int max, boolean isBST){
this.num = num;
this.min = min;
this.max = max;
this.isBST = isBST;
}
}
public int largestBSTSubtree(TreeNode root) {
Result res = helper(root);
return res.num;
}
private Result helper(TreeNode root){
if(root == null){
return new Result(0, Integer.MAX_VALUE, Integer.MIN_VALUE, true);
}
if(root.left == null && root.right == null){
return new Result(1, root.val, root.val, true);
}
Result left = helper(root.left);
Result right = helper(root.right);
if(root.val > left.max && root.val < right.min && left.isBST && right.isBST){
return new Result(1 + left.num + right.num,
Math.min(left.min, root.val),
Math.max(root.val, right.max),
true);
}else{
return new Result(Math.max(left.num, right.num),
Math.min(root.val,
Math.min(left.min, right.min)),
Math.max(root.val,
Math.max(left.max, right.max)),
false);
}
}
}
public class Solution {
class Result {
int res;
int min;
int max;
public Result(int res, int min, int max) {
this.res = res;
this.min = min;
this.max = max;
}
}
public int largestBSTSubtree(TreeNode root) {
Result res = BSTSubstree(root);
return Math.abs(res.res);
}
private Result BSTSubstree(TreeNode root) {
if (root == null) return new Result(0, Integer.MAX_VALUE, Integer.MIN_VALUE);
Result left = BSTSubstree(root.left);
Result right = BSTSubstree(root.right);
if (left.res < 0 || right.res < 0 || root.val < left.max || root.val > right.min) {
return new Result(Math.max(Math.abs(left.res), Math.abs(right.res)) * -1, 0, 0);
} else {
return new Result(left.res + right.res + 1, Math.min(root.val, left.min), Math.max(root.val, right.max));
}
}
}
Without global parameter and can handle MAX and MIN(without MAX__VALUE MIN__VALUE): https://discuss.leetcode.com/topic/36995/share-my-o-n-java-code-with-brief-explanation-and-comments/17
public class Solution {
class Result{
int count;
TreeNode min;
TreeNode max;
boolean valid;
Result(int count, TreeNode min, TreeNode max, boolean valid) {
this.count = count;
this.min = min;
this.max = max;
this.valid = valid;
}
}
public int largestBSTSubtree(TreeNode root) {
Result res = traversal(root);
return res.count;
}
private Result traversal(TreeNode root) {
if (root == null) return new Result(0, null, null, true);
Result left = traversal(root.left);
Result right = traversal(root.right);
if (left.valid && right.valid) {
boolean checkL = true, checkR = true;
if (left.max != null && root.val <= left.max.val) checkL = false;
if (right.min != null && root.val >= right.min.val) checkR = false;
if (checkL && checkR) {
return new Result(left.count + right.count + 1, left.min == null ? root : left.min, right.max == null ? root : right.max, true);
}
}
return new Result(Math.max(left.count, right.count), null, null, false);
}
}