描述
给一棵二叉树，找到有最大平均值的子树。返回子树的根结点。
注意事项
LintCode会打印出根结点为你返回节点的子树，保证有最大平均数子树只有一棵
样例
给一个二叉树：
1
/ \
-5 11
/ \ / \
1 2 4 -2
返回节点 11。
代码
Traverse + Divide Conquer
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
private class ResultType {
public int size;
public int sum;
public ResultType (int sum, int size) {
this.sum = sum;
this.size = size;
}
}
// subtree代表的是当前最大平均数的根结点
// subtreeResult代表当前最大平均数的ResultType
private TreeNode subtree = null;
private ResultType subtreeResult = null;
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);
// result代表当前结点开头的二叉树的数值之和
ResultType result = new ResultType(
left.sum + right.sum + root.val,
left.size + right.size + 1
);
/* 从subtreeResult.sum / subtreeResult.size <
* result.sum / result.size写成下面两端相乘形式来减小精度误差
*/
// result结果和全局最优比较，全局最优是空时直接换成result
if (subtree == null ||
result.sum * subtreeResult.size > subtreeResult.sum * result.size) {
subtree = root;
subtreeResult = result;
}
return result;
}
}