Most Frequent Subtree Sum

Given a binary tree root, find the most frequent subtree sum. The subtree sum of a node is the sum of all values under a node, including the node itself. You can assume there is one unique solution.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Most-Frequent-Subtree-Sum

Examples

Example 1

Input

• root =

Output

• answer = 2

Explanation

2 occurs twice: once as the left leaf, and once as the sum of 2 + 5 - 5.

Solution