Given the root
of a binary tree, find the maximum average value of any subtree of that tree.
(A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.)
Example 1:
Input: [5,6,1]Output: 6.00000Explanation: For the node with value = 5 we have and average of (5 + 6 + 1) / 3 = 4.For the node with value = 6 we have and average of 6 / 1 = 6.For the node with value = 1 we have and average of 1 / 1 = 1.So the answer is 6 which is the maximum.
Note:
- The number of nodes in the tree is between
1
and5000
. - Each node will have a value between
0
and100000
. - Answers will be accepted as correct if they are within
10^-5
of the correct answer.
===================================================================
C#
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 public class Solution { 5 Listavgs = new List (); 6 public double MaximumAverageSubtree(TreeNode root) 7 { 8 int counter = 0; 9 double summer = 0;10 var result = TreeTraverse(root,ref counter,ref summer);11 12 return avgs.Max();13 }14 15 public double? TreeTraverse(TreeNode subTreeRoot,ref int counter,ref double summer)16 {17 if(subTreeRoot == null)18 {19 return null;20 }21 int leftCounter = 0;22 int rightCounter = 0;23 double leftSummer = 0;24 double rightSummer = 0;25 26 double? leftSum = TreeTraverse(subTreeRoot.left,ref leftCounter,ref leftSummer);27 28 if (false == leftSum.HasValue)29 {30 leftSum = 0;31 }32 else33 counter++;34 35 double? rightSum = TreeTraverse(subTreeRoot.right,ref rightCounter,ref rightSummer);36 37 if (false == rightSum.HasValue)38 {39 rightSum = 0;40 }41 else42 counter++;43 44 counter = (leftCounter + rightCounter + 1);45 summer = (leftSummer + rightSummer + subTreeRoot.val);46 avgs.Add(summer / counter);47 48 return subTreeRoot.val;49 }50 }