# [leetcode] Binary Tree Maximum Path Sum

### 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`.

Tags: tree, depth-first-search

10/10/2015 udpate

divide-and-conquer approach

o(n) solution, use a fancy recursion function, do two works together.

It returns the path sum starts from root node to nodes below,

res is the current maximum sum path

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int MININT = 0x8fffffff;
int maxPathSum(TreeNode* root) {
int res = MININT;
pathSum(root, res);
return res;
}
//return the max path sum that starts from root
//res is the maximum path sum in this tree
int pathSum(TreeNode * root, int& res){
if(root == nullptr) return -1;
int left = pathSum(root->left, res);
int right = pathSum(root->right, res);
int tmp = root->val;
tmp = left > 0? tmp + left: tmp;
tmp = right > 0? tmp + right: tmp;
res = max(res, tmp);
return max(max(left, right), 0) + root->val;
}
};```

O(nlogn) solution, not quite efficient, time limit excced.

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int MININT = 0x80000000;
int maxPathSum(TreeNode* root) {
if(root == nullptr){
return MININT;
}
int left = maxPathSum(root->left);
int right = maxPathSum(root->right);
int leftPath = maxToRootSum(root->left);
int rightPath = maxToRootSum(root->right);
int tmp = root->val;
tmp = leftPath > 0? tmp + leftPath: tmp;
tmp = rightPath > 0? tmp + rightPath: tmp;
return max(left, max(right, tmp));
}
int maxToRootSum(TreeNode * root){
if(root == nullptr) return -1;
int left = maxToRootSum(root->left);
int right = maxToRootSum(root->right);
int tmp = root->val;
tmp = max(left, right) > 0? tmp + max(left, right): tmp;
return tmp;
}
};```

Tag里没写divide-and-conquer. 但我还是先想到了一个分治的算法.

C++:

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
/**
* divide and conque
**/

int maxPathSum(TreeNode *root) {
bool isLeftSet = false;
bool isRightSet = false;
//leaf node
if(root->left == NULL && root->right == NULL){
return root->val;
}

else{
if(root->left != NULL){
isLeftSet = true;
leftSum = maxPathSum(root->left);
}
if(root->right != NULL){
isRightSet = true;
rightSum = maxPathSum(root->right);
}
//due to the if condition in line 21, either isLeftSet or isRightSet should be true.
if(isRightSet == false){
//isLeftSet is true
return max(leftSum, max(leftAdjacentSum, 0) + root->val);
}
else if(isLeftSet == false){
//isRightSet is true
return max(rightSum, max(rightAdjacentSum, 0) + root->val);
}
else{
//both isRightSet and isLeftSet is true
//if either the rightAjacentSum or the leftAjacentSum is smaller than 0, discard it.
}

}
}

int maxLeft, maxRight;
bool isLeftSet = false;
bool isRightSet = true;
if(root->left == NULL && root->right == NULL){
return root->val;
}
if(root->left != NULL){
isLeftSet = true;
}
if(root->right != NULL){
isRightSet = true;
}

if(isRightSet == false){
return max(maxLeft, 0) + root->val;
}
else if(isLeftSet == false){
return max(maxRight, 0) + root->val;
}
else{
return max(max(maxRight, maxLeft), 0) + root->val;
}
}
};```

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class ReturnValue{
public:
int maxPathSum;
};
class Solution {
public:
/**
* divide and conquer
**/
int maxPathSum(TreeNode *root){
return _maxPathSum(root)->maxPathSum;
}

ReturnValue * _maxPathSum(TreeNode *root) {
bool isLeftSet = false;
bool isRightSet = false;
ReturnValue * p;
//leaf node
if(root->left == NULL && root->right == NULL){
return new ReturnValue(root->val, root->val);
}

else{
if(root->left != NULL){
isLeftSet = true;
p = _maxPathSum(root->left);
leftSum = p->maxPathSum;
}
if(root->right != NULL){
isRightSet = true;
p = _maxPathSum(root->right);
rightSum = p->maxPathSum;
}
//due to the if condition in line 21, either isLeftSet or isRightSet should be true.
if(isRightSet == false){
//isLeftSet is true
int thisMaxPathSum = max(leftSum, max(leftAdjacentSum, 0) + root->val);

}
else if(isLeftSet == false){
//isRightSet is true
int thisMaxPathSum = max(rightSum, max(rightAdjacentSum, 0) + root->val);

}
else{
//both isRightSet and isLeftSet is true
//if either the rightAjacentSum or the leftAjacentSum is smaller than 0, discard it.
int thisMaxPathSum =  max(max(leftSum, rightSum), max(leftAdjacentSum, 0) + max(rightAdjacentSum, 0) + root->val);