Practice/Meta/Leetcode 1448. Count Good Nodes in Binary Tree

Leetcode 1448. Count Good Nodes in Binary Tree

CodingOptional

Problem

Given the root of a binary tree, count the number of superior nodes in the tree.

A node is considered superior if its value is greater than or equal to all values encountered on the path from the root to that node (inclusive of the node itself).

The root node is always considered superior since there are no preceding nodes on its path.

Requirements

1. Traverse the entire binary tree and examine each node
2. Track the maximum value encountered along the path from root to each node
3. Count nodes whose values are greater than or equal to the path maximum
4. Return the total count of superior nodes

Constraints

• The number of nodes in the tree is in the range [1, 10^5]
• Node values are in the range [-10^4, 10^4]
• The tree may contain duplicate values
• The tree may contain negative values

Examples

Example 1:

` Input: root = [3,1,4,3,null,1,5] 3 /
1 4 / /
3 1 5 Output: 4 Explanation:

• Node 3 (root): superior (no predecessors)
• Node 1 (left child): not superior (3 > 1)
• Node 4 (right child): superior (4 >= 3)
• Node 3 (left-left): superior (3 >= max(3,1))
• Node 1 (right-left): not superior (1 < max(3,4))
• Node 5 (right-right): superior (5 >= max(3,4)) Total: 4 superior nodes `

Example 2:

Input: root = [7] Output: 1 Explanation: A single node is always superior.

Example 3:

Input: root = [1,2,3] 1 / \ 2 3 Output: 3 Explanation: All nodes are superior since 2 >= 1 and 3 >= 1.