Graph Theory37 sections · 1633 units
Open in Course

LeetCode 124 Binary Tree Maximum Path Sum - State Definition

Max downward path from node

Define ext{dp}[v] = maximum path sum starting at vv and going down into one of its subtrees (not both). Also track a global variable extmaxPath ext{maxPath} = best path sum found anywhere in the tree. At each node, update extmaxPath ext{maxPath} by considering the path that goes through that node using both subtrees.

Return ext{dp}[v] to the parent for its calculation. The returned value and the tracked answer serve different purposes.