535. Second Smallest Badge
In a knockout tournament, each match is a node of the binary tree root and the leaves are the players, each holding a positive badge number. Every internal node has exactly two children, and its value is the smaller of its two children's values, which is the badge that advances. Consequently the root holds the smallest badge in the whole tree. Return the second smallest distinct badge value found anywhere in the tree. If all the values in the tree are equal, so no second smallest exists, return -1.
Example 1
- Input:
- root = [4,4,6,4,9,6,7]
- Output:
- 6
- Explanation:
The distinct values are 4, 6, 7 and 9, so the second smallest is 6.
Example 2
- Input:
- root = [10,10,10]
- Output:
- -1
- Explanation:
Every value equals 10, so there is no second smallest value and the answer is -1.
Example 3
- Input:
- root = [5,5,13,5,8,13,20]
- Output:
- 8
- Explanation:
The distinct values are 5, 8, 13 and 20, so the answer is 8.
Constraints
1 ≤ number of nodes ≤ 500
1 ≤ Node.val ≤ 231 - 1
Every node has either 0 or 2 children, and each non-leaf node's value equals the minimum of its two children's values.
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)