904. Count Good Nodes in Binary Tree

Given the root of a binary tree, a node X is 'good' if no node on the path from the root to X has a value strictly greater than X. Return the number of good nodes. The root is always good. The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Integer — the number of good nodes.

Examples

Input: [3,1,4,3,null,1,5]
Output: 4
Explanation: Good nodes: 3 (root), 4, 5, and the deeper 3.

Input: [3,3,null,4,2]
Output: 3
Explanation: Three good nodes.

Input: [1]
Output: 1
Explanation: Root is good.

Constraints

• 1<=nodes<=10^5
• -10^4<=value<=10^4

Asked by