A network of hiking trails branches out from a trailhead and never rejoins, so it forms a binary tree: every node is a spot on the trail and node.val is its altitude. You always hike from the trailhead (the root) straight down to a spot. A spot is a lookout point when nothing you passed on the way there, starting with the trailhead, was higher than it. Ties are fine: a spot at the same altitude as the highest point so far still counts. The trailhead is always a lookout point.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write count_lookouts(root) -> int: the number of lookout points. An empty tree (None) has none.
# 3
# / \
# 1 4
# / / \
# 3 1 5
count_lookouts(root) # 4: the root 3, the lower 3 (path 3, 1, 3), then 4 and 5
count_lookouts(None) # 0
- Up to 150,000 nodes; altitudes are integers between
-10^4and10^4. - Trees can be up to 3,000 levels deep. If you recurse, raise the limit first (
sys.setrecursionlimit(10_000)), or use an explicit stack. - Aim for O(n). Looking back up the whole path from every spot is too slow on tall trees.
Show hint
On the way down, carry along the highest altitude seen so far on the current path.