Binary Tree Maximum Path Sum Problem

Problem Description
Level: medium
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:

return 6


1. Consider divide and conquer algorithm
2. for any root, left and right side will have a max path [from a node (may be root / child node)], to a linked node [may be root / child node)], also include a single path (from root to a child node, then next child node etc)
3. pick up the maximum value of the max path (left and right), assume the result is V1
4. calculate the left single path + right single path + root value (will be a potential max path), assume the result is V2
5. compare V1 and V2, and choose the max value in V1 and V2 as the new the max path value.



Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditShare on StumbleUponEmail this to someoneShare on TumblrDigg this

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">