You are given a binary tree root. Return the most frequent subtree sum.
The subtree sum of a node is the sum of its own value and the values of all of its descendants. Every node has exactly one subtree sum, so there are n subtree sums in total, counted with repetition (one per node).
You can assume exactly one sum occurs most often.
Tree Encoding
Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.
The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the input is displayed; the decoding is done for you.
Constraints
The number of nodes in root is in the range [1,105].
−104≤Node.val≤104
Exactly one subtree sum occurs most often.
Examples
Example 1
Input
root = [5, 2, -5]
root
Output
2
Explanation
The subtree sums are `2` (the left leaf), `-5` (the right leaf), and `5 + 2 + (-5) = 2` (the root). `2` occurs twice and every other sum occurs once, so `2` is the most frequent.
Example 2
Input
root = [1]
root
Output
1
Explanation
The single node has one subtree sum, its own value `1`, which is trivially the most frequent.
Example 3
Input
root = [0, 0, 0]
root
Output
0
Explanation
Every node has value `0`, so every subtree sum is `0`. All three sums are `0`, making it the most frequent.
Loading editor...
Run checks the sample cases; Submit runs every case.
Samples 3
Custom 0
passedwrong answertime limiterrorran, no expected valuenot run