1448. Count Good Nodes in Binary Tree

A node X in a binary tree is good if no node on the path from the root to X has a value greater than X. Return the number of good nodes.

Same rule, iteratively: the queue holds each node together with the max on the path to it.

1function goodNodes(root: TreeNode | null): number {
2  if (!root) return 0;
3  const queue: [TreeNode, number][] = [[root, -Infinity]];
4  let good = 0;
5  while (queue.length) {
6    const [n, max] = queue.shift()!;
7    if (n.val >= max) good++;
8    const m = Math.max(max, n.val);
9    if (n.left) queue.push([n.left, m]);
10    if (n.right) queue.push([n.right, m]);
11  }
12  return good;
13}

good = 0

tree

queue (node, max)

3, −∞

Queue the root with max = −∞.

1 / 0

Space: play/pause · ←/→: step