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.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

C++:
01 /**
02  * Definition for binary tree
03  * struct TreeNode {
04  *     int val;
05  *     TreeNode *left;
06  *     TreeNode *right;
07  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
08  * };
09  */
10 int maxPathSumHelper(TreeNode *root, int& max)
11 {
12     if(root==NULL)
13         return 0;
14     int left=maxPathSumHelper(root->left,max);
15     int right=maxPathSumHelper(root->right,max);
16     int value=root->val;
17     int localMax=left+right+value;
18     if(localMax>max)
19         max=localMax;
20     int localPath=left>right?left:right;
21     localPath+=value;
22     return localPath>0?localPath:0;
23 }
24 class Solution {
25 public:
26     int maxPathSum(TreeNode *root) {
27         // Start typing your C/C++ solution below
28         // DO NOT write int main() function
29         if(root==NULL)
30             return 0;
31         int max=root->val;
32         maxPathSumHelper(root,max);
33         return max;
34     }
35 };
Advertisements
This entry was posted in Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s