539. Ancestor Gap
A salary hierarchy is stored as a binary tree root where each node holds an employee's non-negative pay. For two nodes a and d where a is a proper ancestor of d (a lies on the path from the root to d and is a different node), the drop is a.val - d.val, counted only when it is positive. Return the largest drop over all such ancestor-descendant pairs. If no ancestor earns more than one of its descendants, or the tree has fewer than two nodes, return 0.
Example 1
- Input:
- root = [15,9,20,12,3,null,8]
- Output:
- 12
- Explanation:
The pair 15 (root) and 3 gives a drop of 12, as does 20 and 8; no pair does better.
Example 2
- Input:
- root = [1,2,3,4]
- Output:
- 0
- Explanation:
Every ancestor is smaller than its descendants, so no drop is positive and the answer is 0.
Example 3
- Input:
- root = [10,4,null,7,1]
- Output:
- 9
- Explanation:
The root 10 and the leaf 1 give the largest drop, 9.
Constraints
0 ≤ number of nodes ≤ 500
0 ≤ Node.val ≤ 105
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)