search

benluiwj / DailyCodingProblems

0 stars 0 forks source link

TREE REVISION QUESTIONS #1

Open benluiwj opened 2 years ago

benluiwj commented 2 years ago
benluiwj commented 2 years ago

Have a global variable that maintains the biggest sum path. So in each case, we either have a path that goes through the root (L + C + R) or a path that only includes either L or R, depending on which is greater. The return value should be a path through the root. Neetcode Solution

This question very important

benluiwj commented 2 years ago

House Robber iii

DSA: DFS

Idea:

Maintain a pair, <withRoot, withoutRoot>. for each node, perform it on left and right subtree. Then at the current node, to calculate withRoot, use withRoot + withoutRootLeft + withoutRootRight. To calculate withoutRoot, sum the maximum of each pair.

At the root, return the max of either

ps. was quite close. second element of the pair was wrong.