1120. Maximum Average Subtree π
Description
Given the root
of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10-5
of the actual answer will be accepted.
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: root = [5,6,1] Output: 6.00000 Explanation: For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4. For the node with value = 6 we have an average of 6 / 1 = 6. For the node with value = 1 we have an average of 1 / 1 = 1. So the answer is 6 which is the maximum.
Example 2:
Input: root = [0,null,1] Output: 1.00000
Constraints:
- The number of nodes in the tree is in the range
[1, 104]
. 0 <= Node.val <= 105
Solutions
Solution 1: Recursion
We can use a recursive method. For each node, we calculate the sum and count of the nodes in the subtree rooted at that node, then calculate the average, compare it with the current maximum, and update the maximum if necessary.
Therefore, we design a function dfs(root)
that represents the sum and count of nodes in the subtree rooted at root
. The return value is an array of length 2, where the first element represents the sum of nodes, and the second element represents the count of nodes.
The recursive process of the function dfs(root)
is as follows:
- If
root
is null, return[0, 0]
; - Otherwise, calculate the sum and count of nodes in the left subtree of
root
, denoted as[ls, ln]
; calculate the sum and count of nodes in the right subtree ofroot
, denoted as[rs, rn]
. The sum of nodes in the subtree rooted atroot
isroot.val + ls + rs
, and the count of nodes is1 + ln + rn
. Calculate the average, compare it with the current maximum, and update the maximum if necessary; - Return
[root.val + ls + rs, 1 + ln + rn]
.
Finally, return the maximum value.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
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 27 28 29 30 31 32 33 34 35 |
|
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 27 28 29 30 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|