Count Good Nodes in Binary Tree
A node is good when no value on the path from the root to it is greater than its value. Count all good nodes, including the root.
Work through the cases
3 examplesInput notation
A binary tree in level order on one line, using null for missing children. Omit trailing nulls; use null for an empty tree.Expected result
The good-node count.Case 1
Input
3 1 4 3 null 1 5
Expected output
4
Case 2
Input
2 2 2
Expected output
3
Case 3
Input
null
Expected output
0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
A node is good if nothing larger appears on the path from the root. n ≤ 10^5. DFS carries the path maximum mx; count the node when its value is at least mx, then update mx.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans = 0;
public int goodNodes(TreeNode root) {
dfs(root, -100000);
return ans;
}
private void dfs(TreeNode root, int mx) {
if (root == null) {
return;
}
if (mx <= root.val) {
++ans;
mx = root.val;
}
dfs(root.left, mx);
dfs(root.right, mx);
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.