486. Unbeaten Nodes
In a company org chart drawn as a binary tree, each node holds an employee's seniority score. An employee is called unbeaten if none of their ancestors (the employees on the path from the root down to, but not including, that employee) has a strictly higher score. The root has no ancestors, so it is always unbeaten. Ties do not count against anyone: an ancestor with an equal score does not beat the employee.
Given the root of the tree as root, return how many employees are unbeaten. An empty tree contains none. Note that the tree can be very deep, so a solution should avoid relying on deep recursion.
Example 1
- Input:
- root = [5,3,8,2,4,9,1]
- Output:
- 3
- Explanation:
The unbeaten nodes are 5, 8 and 9; every other node has a strictly larger ancestor.
Example 2
- Input:
- root = [4,4,4,4]
- Output:
- 4
- Explanation:
All scores are equal, and equal ancestors do not beat anyone, so all four nodes are unbeaten.
Example 3
- Input:
- root = [-2,-5,-1,-3,null,-1]
- Output:
- 3
- Explanation:
The unbeaten nodes are the root -2 and the two -1 nodes on the right branch.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ Node.val ≤ 1000
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(n)