Tree Path and Tree DP

Opening scenario

Problem references use LC for LeetCode.

Binary Tree Maximum Path Sum (LC 124): a path is any sequence of connected nodes (it need not pass through the root and need not go through any particular node); return the maximum sum over all paths. Follow-up you should expect: Path Sum III (LC 437) — count the downward paths whose values sum to a target. A path may start at any node and end at any node below it.

For maximum path sum, the tree and the selected path must be non-empty, and no node may repeat on a path. The templates use nodes with val, left, and right fields. The root-to-leaf number example below assumes digit values 0..9; good_nodes assumes a non-empty tree and counts nodes whose value is at least every value on their root-to-node path. Start by separating information passed down from information returned up.

Question progression

Q1 — Root-to-leaf sums: what does a node need from above vs from below?

Question: In…