[LintCode] Problem 597 - Subtree with Maximum Average

Posted on | In ,

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

Note

It’s guaranteed that there is only one subtree with maximum average.

Example

No.1

Input：

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

Output：11(it’s a TreeNode)

No.2

Input：

1
2
3
    1
  /   \
-5     11

Output：11(it’s a TreeNode)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

private class ResultType{
    int sum;
    int num;
    ResultType(int sum, int num) {
        this.sum = sum;
        this.num = num;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private TreeNode maxTree;
private ResultType maxResult;

public TreeNode findSubtree2(TreeNode root) {
    findSubtreeHelper(root);
    return maxTree;
}

private ResultType findSubtreeHelper(TreeNode node) {
    if (node == null)
        return new ResultType(0, 0);

    ResultType left = findSubtreeHelper(node.left);
    ResultType right = findSubtreeHelper(node.right);

    int sum = left.sum + right.sum + node.val;
    int num = left.num + right.num + 1;
    ResultType root = new ResultType(sum, num);

    if (maxTree == null || maxResult.sum * root.num < root.sum * maxResult.num) {
        maxTree = node;
        maxResult = root;
    }

    return root;
}