Count Good Nodes in Binary Tree

Count Good Nodes in Binary Tree

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Examples

Example 1:

Input: root = [3, 1, 4, 3, null, 1, 5]
Output: 4
Explanation: Nodes 3 (root), 3 (left-left), 4, and 5 are good.

        3
       / \
      1   4
     /   / \
    3   1   5

Example 2:

Input: root = [3, 3, null, 4, 2]
Output: 3
Explanation: Nodes 3 (root), 3 (left), and 4 are good.

Example 3:

Input: root = [1]
Output: 1

Constraints

• The number of nodes in the tree is in the range [1, 10^5].
• -10^4 <= Node.val <= 10^4

Expected Complexity

• Time: O(n)
• Space: O(h) where h is the height of the tree