# Leetcode 124 - Binary tree maximum path sum

`Note:`

- We def need to use
`DFS`

, but what should we return in each recursion? - Consider these 3 situations:
- For each node, we need to have 3 info to decide whether we should only
`pick the node`

or`extend to its subtrees`

. - Base case: return
`[0, 0, 0]`

. - Normally, return
`max = [nodeVal, nodeVal + maxLeftSubtreeSum, nodeVal + maxRightSubtreeSum]`

; - Don’t really need
`memo`

because there is`no repetitive calculations`

. - Need to set a
`res`

variable, so we can compare with it for every node during recursions. `res = max(res, nodeVal, nodeVal + leftSum, nodeVal + rightSum, nodeVal + leftSum + rightSum)`

.- What I learned from this HARD DFS question?
- Always know what you are gonna return in DFS.
- Consider simple cases to build your DFS.
- Don’t care about details too much, and don’t overthink!

`Question:`

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

`Example:`

1 | Input: root = [1,2,3] |

`Code:`

1 | /** |