I’ve just solved one more problem from leetcode and going to share that solution. So, solved problem calls Binary Tree Maximum Path Sum.

Problem description:

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:

Given the below binary tree,

[crayon-5ba7f4b5f1568424385292/] Return`6`

.

**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 ???

*null*return (the max path equals to ) and go to the right node, again if node is

*null*return and go up to parent. Parent is

*2*. We should check what is the max path

*or*

**left +parent***. After that check if this*

**right +parent****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 …

[crayon-5ba7f4b5f1578363234390/]
So, that is all, if you have some questions don’t hesitate to ask me 🙂

Cheers !!!