Amazon Online Assessment (OA) - Subtree with Maximum Average
Given a tree, find the subtree with the maximum average. Return the subtree's root's value. Note that the tree could have arbitrarily many children.
Example 1:
Input:
Output: 12
Explanation
The sum of each subtree:
The subtree max average is 9.3 and the root is the node with value 12, so we return 12.
Try it yourself
Explanation
Prereq: DFS on Tree, DFS on ternary tree
This is a pretty straightforward question - we traverse the tree and the sum and number of nodes in the subtree to the parent.
1 | + |
| |||
2 | + |
| |||
3 | + | ||||
1 | 4 |
| |||
2 | 5 |
| |||
3 | 6 |
| |||
Expand 2 lines ... | |||||
6 | 9 |
| |||
7 | 10 | ||||
8 | 11 |
| |||
9 | - |
| |||
12 | + |
| |||
10 | - |
| |||
13 | + |
| |||
11 | 14 | ||||
12 | 15 | ||||
16 | + |
| |||
17 | + |
| |||
18 | + |
| |||
19 | + |
| |||
20 | + |
| |||
21 | + |
| |||
22 | + |
| |||
23 | + |
| |||
24 | + | ||||
25 | + |
| |||
26 | + |
| |||
27 | + | ||||
13 | 28 |
| |||
14 | 29 |
| |||
15 | 30 |
| |||
16 | 31 |
| |||
17 | 32 |
| |||
Expand 5 lines ... |
Loading full content...