Count good nodes
You get the root of a binary tree of integers, with at least one node. Picture walking from the root down to some node. That node is good if none of the nodes you passed on the way holds a bigger value than it does. A tie is fine, and the root is always good because you pass nothing on the way to it.
Return the number of good nodes.
Examples write a tree level by level, left to right, with None where a child is missing.
root = [5, 3, 7, 6, 1, None, 7]Output4The good nodes are 5, 6, 7 and the lower 7. The 3 and the 1 have 5 above them. The 6 is good because it is at least as large as both 3 and 5. The lower 7 ties the 7 above it, which is allowed.
root = [-1, -5, 2, None, None, 0, 3]Output3-1, 2 and 3 are good. -5 has -1 above it, and 0 has 2 above it.
root = [8]Output1The root is always good.
1 ≤ number of nodes ≤ 5 × 105
The tree is at most 900 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
-104 ≤ val ≤ 104
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.