- 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 nodeor
extend to its subtrees.
- Base case: return
[0, 0, 0].
- Normally, return
max = [nodeVal, nodeVal + maxLeftSubtreeSum, nodeVal + maxRightSubtreeSum];
- Don’t really need
memobecause there is
no repetitive calculations.
- Need to set a
resvariable, 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!
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.
Input: root = [1,2,3]