Asked at
Count Good Nodes In Binary Tree
MediumVerifiedTreeDFSRecursion~20 min
Given the root of a binary tree, count the good nodes. A node is good if no node on the path from the root to it has a strictly larger value.
The root is always good. A node is { val, left, right } with null children; the whole empty tree is null. The input arrives as the root node directly.
Examples
in{val:3, left:{val:1, left:{val:3}}, right:{val:4, left:{val:1}, right:{val:5}}}
out4
Nodes 3, 3, 4, 5 have no larger ancestor on their path.
in{val:1, left:null, right:null}
out1
The root is always good.
Constraints
- 1 ≤ number of nodes ≤ 10⁵
- -10⁴ ≤ node.val ≤ 10⁴
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.