510. Most Common Keys
A survey stores answers in a binary search tree that is allowed to hold repeated values: for every node, all keys in its left subtree are less than or equal to the node's key and all keys in its right subtree are greater than or equal to it. An in-order reading is therefore sorted in non-decreasing order.
Given root, find the key or keys that occur most often in the tree. Return all of them in increasing order, each listed once. If several different keys tie for the highest count, return all of them. For an empty tree, return an empty array.
Example 1
- Input:
- root = [4,2,6,2,null,null,6]
- Output:
- [2,6]
- Explanation:
The in-order keys are 2, 2, 4, 6, 6; the values 2 and 6 each appear twice, more often than 4.
Example 2
- Input:
- root = [1,null,2,2]
- Output:
- [2]
- Explanation:
The in-order keys are 1, 2, 2, so 2 is the only most frequent key.
Constraints
0 ≤ number of nodes ≤ 104
-109 ≤ Node.val ≤ 109
The tree satisfies left subtree keys ≤ node key ≤ right subtree keys at every node.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)