Count Good Nodes in Binary Tree

You get the root of a binary tree. Return how many good nodes the tree has.

A node is good if no node on its path from the root has a greater value.

Ties are fine: a node equal to the largest value above it is good. The root is always good.

The trees below are listed level by level, top to bottom and left to right. A missing child is written as null.

Example 1:

      5
     / \
    2   8
   /   / \
  6   7   9

Input: root = [5,2,8,6,null,7,9]
Output: 4
Explanation: The good nodes are 5, 8, 9 and 6.
On the way 5 → 2 → 6, no value is greater than 6.
The 2 is not good, because 5 is greater.
The 7 is not good, because 8 is greater.

Example 2:

     -1
     /  \
   -1    -3
     \
      0

Input: root = [-1,-1,-3,null,0]
Output: 3
Explanation: The root -1 is good.
The -1 under it is good too, since equal is not greater.
The 0 is good, since nothing above it is greater.
The -3 is not good, because the root -1 is greater.

Example 3:

      9
     /
    4
   /
  1

Input: root = [9,4,null,1]
Output: 1
Explanation: Every value below the root is smaller than 9.
So only the root is good.

Constraints:

• 1 to 100,000 nodes.
• Each value is from -10,000 to 10,000.
• The tree is at most 800 levels deep.