Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 1448 Count Good Nodes in Binary Tree - Problem Statement

Path maximum tracking

A node is "good" if no node on the path from root to it has a greater value. Count good nodes. This is a top-down tree DP (pre-order).

Carry the maximum value seen on the path so far. At each node: if valpathMaxval \geq pathMax, it's good. Update pathMax=max(pathMax,val)pathMax = \max(pathMax, val) for children. Unlike most tree DP which is bottom-up, this uses parent information, so it's top-down. The state flows from root to leaves.