Dfs

Subtitle / Summary The constraint “the path can start anywhere, but must go downward” makes root-to-leaf DP insufficient. This ACERS guide explains prefix sums on trees: convert any downward path into a difference of two prefix sums, maintain a frequency hash map during one DFS, and finish in O(n). Reading time: 12–15 min Tags: binary tree, prefix sum, DFS, hash map SEO keywords: Path Sum III, tree prefix sum, prefix-sum hash, LeetCode 437 Meta description: Count downward paths whose sum equals targetSum in O(n) via prefix sum + hash map, with derivation, tradeoffs, and multi-language implementations. Target Readers LeetCode learners who want a reusable “tree + hash map” template People who tend to write O(n²) when the path does not have to start at the root Engineers working with hierarchical data (call traces, org trees) who need “downward segment” statistics Background / Motivation Many “tree path” problems hide a trap: you naturally assume paths start at the root, or end at leaves — but this problem allows the path to start and end at any nodes, as long as the direction is downward (parent → child). ...