Subtree with Maximum Average

Subtree with Minimum Sum (LC.596)

Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.

Example

+    1
   /   \
 -5     2
 / \   /  \
0   2 -4  -5

root 1 has the minSubtree.

Analysis

Divide and conquer does not work well for this kind of problem. You need to somehow traverse it. (need a global value).

Code

private TreeNode minSubtree = null;
private int minSum = Integer.MAX_VALUE;
/**
 * @param root the root of binary tree
 * @return the root of the minimum subtree
 */
public TreeNode findSubtree(TreeNode root) {
    subtreeSum(root);
    return minSubtree;
}
private int subtreeSum(TreeNode root) {
    // base case
    if (root == null) {
        return 0;
    }
    // divide & conquer
    int currentSum = root.val + subtreeSum(root.left) + subtreeSum(root.right);
    // update global value
    if (currentSum < minSum) {
        minSum = currentSum;
        minSubtree = root;
    }
    return currentSum;
}

Subtree with Maximum Average (LC.597)

Given a binary tree, find the subtree with maximum average. Return the root of the subtree.

Example

+    1
   /   \
 -5     11
 / \   /  \
1   2 4    -2

Root 11's subtree.

Analysis

Again we need D&C with a global value. What's the return type for D&C and what to keep track as a global value?

Code