Leetcode 124: Binary Tree Maximum Path Sum

The key here is that a single path through a node (through one child of the node rather than two) is fairly easily handled by using bottom up preorder traversal and checking which is bigger out of the left and right branch. The complication is if the path goes from one child through the parent to the other child. In that scenario the thing to realise is that the path cost is completely known at that stage as it consists of left branch cost + right branch cost. It does not go up at all. So we need to keep track of that dual child cost separately and I used a reference parameter maxCost for that. I included the single path cost in the maxCost calculation also, so maxCost is the final result.

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.