Count Good Nodes in Binary Tree

Given the root of a binary tree, return the number of good nodes in the tree. A node is good if on the path from the root to that node there are no nodes with a value greater than it. Pattern focus: Preorder DFS (Root First). Carry the current maximum value from the root to the node.

Input Format

root = binary tree root

Output Format

number of good nodes

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [3,1,4,3,null,1,5]

Output:

4

Explanation:

The good nodes are 3, 4, 3, and 5.

Example 2:

Input:

root = [3,3,null,4,2]

Output:

3

Explanation:

Every node on the left spine is at least the maximum seen so far.

Loading...
Count Good Nodes in Binary Tree - Binary Tree