I’ve just solved one more problem from leetcode and going to share that solution. So, solved problem calls Binary Tree Maximum Path Sum.
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
Given the below binary tree,
OK, stop and think
…. What do we have ??? The main point is binary tree. We can use perfect traversing
algorithms. In our case we need to use post order
traversal, is not it ? OK, good, if we got left, right and current what we should check ???
We should understand how post order is working . Tree should be like that:
We will traverse to the left, check if node is null
(the max path equals to
) and go to the right node, again if node is null
and go up to parent. Parent is 2
. We should check what is the max path left +parent
or right +parent
. After that check if this max path
biggest that current value
(because left or right can be negative).
Good, after that we will have max current path in other words max path for current value. So, after that we should check what is the bigger max current path or full path (full path is left + current + right, because the path can start and end at any node) and if that value biggest that stored set it like a max path. That is all, so, words are good but better code, let’s go …
So, that is all, if you have some questions don’t hesitate to ask me 🙂