描述
給一棵二叉樹鹃愤，找到有最大平均值的子樹。返回子樹的根結(jié)點(diǎn)叫挟。
注意事項(xiàng)
LintCode會(huì)打印出根結(jié)點(diǎn)為你返回節(jié)點(diǎn)的子樹峡扩，保證有最大平均數(shù)子樹只有一棵
樣例
給一個(gè)二叉樹：
1
/ \
-5 11
/ \ / \
1 2 4 -2
返回節(jié)點(diǎn) 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代表的是當(dāng)前最大平均數(shù)的根結(jié)點(diǎn)
// subtreeResult代表當(dāng)前最大平均數(shù)的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代表當(dāng)前結(jié)點(diǎn)開頭的二叉樹的數(shù)值之和
ResultType result = new ResultType(
left.sum + right.sum + root.val,
left.size + right.size + 1
);
/* 從subtreeResult.sum / subtreeResult.size <
* result.sum / result.size寫成下面兩端相乘形式來減小精度誤差
*/
// result結(jié)果和全局最優(yōu)比較拖陆，全局最優(yōu)是空時(shí)直接換成result
if (subtree == null ||
result.sum * subtreeResult.size > subtreeResult.sum * result.size) {
subtree = root;
subtreeResult = result;
}
return result;
}
}