Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3] 1 / \ 2 3 Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]   -10    / \   9  20     /  \    15   7 Output: 42

Solution

Here we can do post order tree traversal, Before visiting current node, calculate maximum sum from left and right sub tree. Check if current_node+right_max+left_max is giving grater sum compare to previously found sum.

Code

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *