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,

123 1/ \2 3Return

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

1 2 3 4 5 |
1 / \ 2 3 / \ / \ null null null |

We will traverse to the left, check if node is *null* return *0* (the max path equals to *0* ) and go to the right node, again if node is *null* return *0* and go up to parent. Parent is *2*. We should check what is the max path * left +parent* or

*. 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 …

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public int maxPathSum(TreeNode root) { Integer max[] = new Integer[1]; maxPathSum(root, max); return max[0]; } public int maxPathSum(TreeNode root, Integer[] max) { if (root == null) { return 0; } int left = maxPathSum(root.left, max); int right = maxPathSum(root.right, max); int current = root.val; // choose biggest path for return int maxCurrentPath = max(current, max(left+current, right+current)); if (max[0] == null) max[0] = current; else { // choose max path int fullPath = left + current + right; max[0] = max(max[0], max(maxCurrentPath, fullPath)); } return maxCurrentPath; } |

So, that is all, if you have some questions don’t hesitate to ask me 🙂

Cheers !!!