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：
Output：11(it’s a TreeNode)
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class {
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;
}
|
近期评论