Subtree with Maximum Average

本文主要是介绍Subtree with Maximum Average，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

python:一定要注意，除法的精度问题。leetcode中不一定使用的是python3.X

"""
Definition of TreeNode:
class TreeNode:def __init__(self, val):this.val = valthis.left, this.right = None, None
"""
class Solution:# @param {TreeNode} root the root of binary tree# @return {TreeNode} the root of the maximum average of subtreeavg, node = 0, Nonedef findSubtree2(self, root):# Write your code hereif root is None:return Noneself.getSubtree(root)return self.node;def getSubtree(self, root):if root is None:return 0, 0sumLeft, countLeft = self.getSubtree(root.left)sumRight, countRight = self.getSubtree(root.right)sumRoot = sumLeft + sumRight + root.valcountRoot = countLeft + countRight + 1average = sumRoot * 1.0 / countRoot if self.node is None or average > self.avg:self.avg = averageself.node = rootreturn sumRoot, countRoot

Java

/*** 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;*     }* }*/
class ResultType {public int sum;public int count;public double avg;public TreeNode node;public ResultType(int sum, int count, double avg, TreeNode node) {this.sum = sum;this.count = count;this.node = node;this.avg = avg;}
}
public class Solution {/*** @param root the root of binary tree* @return the root of the maximum average of subtree*/private double avger = Integer.MIN_VALUE;private TreeNode node = null;public TreeNode findSubtree2(TreeNode root) {// Write your code hereif (root == null) {return null;}getSubtree(root);return node;}private ResultType getSubtree(TreeNode root) {if (root == null) {return new ResultType(0, 0, 0, null);}ResultType left = getSubtree(root.left);ResultType right = getSubtree(root.right);int sum = root.val + left.sum + right.sum;int num = 1 + left.count + right.count;if (avger < (double)sum / num) {avger = (double)sum / num;node = root;}return new ResultType(sum, num, (double)sum / num, root);}
}

这篇关于Subtree with Maximum Average的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---