Description
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
root = [3,1,4,3,null,1,5]4Nodes 3, 3, 4, 5 are good.
root = [2,1,3,-1,2,4,6]5Starting from root 2: Node 2 is good (root). Left subtree: Node 1 is not good (2 > 1), Node -1 is not good (2 > -1), Node 2 is good (path maximum is 2). Right subtree: Node 3 is good (3 > 2), Node 4 is good (4 > 3), Node 6 is good (6 > 4). Good nodes: 2, 2, 3, 4, 6.
root = [5,5,5,null,5,5]5All nodes have the same value 5. Starting from root 5: Root is good. Left child 5 is good (5 >= 5). Right child 5 is good (5 >= 5). The right child of left node 5 is good (path maximum is 5). The left child of right node 5 is good (path maximum is 5). All 5 nodes are good since no ancestor is strictly greater.
Constraints
- •
Number of nodes is in range [1, 10⁵] - •
-10⁴ ≤ Node.val ≤ 10⁴