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);
        }
    }

}

https://discuss.leetcode.com/topic/36995/share-my-o-n-java-code-with-brief-explanation-and-comments/2

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);
    }
}

results matching ""

    No results matching ""