# Binary Tree Maximum Path Sum

## Question

### Problem Statement

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

#### Example

Given the below binary tree:

  1
/ \
2   3


return 6.

## 题解1 - 递归中仅返回子树路径长度

Warning 注意区分包含根节点的路径和(题目要的答案)和左子树/右子树部分的路径长度(答案的一个组成部分)。路径和=根节点+左子树路径长度+右子树路径长度

       -10
/  \
2    -3
/ \   / \
3   4 5   7


Time Limit Exceeded

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int maxPathSum(TreeNode *root) {
if (NULL == root) {
return 0;
}

int result = INT_MIN;
stack<TreeNode *> s;
s.push(root);
while (!s.empty()) {
TreeNode *node = s.top();
s.pop();

int temp_path_sum = node->val + singlePathSum(node->left) \
+ singlePathSum(node->right);

if (temp_path_sum > result) {
result = temp_path_sum;
}

if (NULL != node->right) s.push(node->right);
if (NULL != node->left) s.push(node->left);
}

return result;
}

private:
int singlePathSum(TreeNode *root) {
if (NULL == root) {
return 0;
}

int path_sum = max(singlePathSum(root->left), singlePathSum(root->right));
return max(0, (root->val + path_sum));
}
};


## 题解2 - 递归中同时返回子树路径长度和路径和

### C++ using std::pair

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
private:
pair<int, int> helper(TreeNode *root) {
if (NULL == root) {
return make_pair(0, INT_MIN);
}

pair<int, int> leftTree = helper(root->left);
pair<int, int> rightTree = helper(root->right);

int single_path_sum = max(leftTree.first, rightTree.first) + root->val;
single_path_sum = max(0, single_path_sum);

int max_sub_sum = max(leftTree.second, rightTree.second);
int max_path_sum = root->val + leftTree.first + rightTree.first;
max_path_sum = max(max_sub_sum, max_path_sum);

return make_pair(single_path_sum, max_path_sum);
}

public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
int maxPathSum(TreeNode *root) {
if (NULL == root) {
return 0;
}

return helper(root).second;
}
};


### 源码分析

The path may start and end at any node in the tree.

1. 采用「冒泡」法返回不经过根节点的路径和的较大值。
2. 递推子树路径长度(不变值)而不是到该节点的路径和(有可能变化)，从而保证了这种解法的正确性。

### C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
class ResultType {
public:
int singlePath, maxPath;
ResultType(int s, int m):singlePath(s), maxPath(m) {}
};

private:
ResultType helper(TreeNode *root) {
if (root == NULL) {
ResultType *nullResult = new ResultType(0, INT_MIN);
return *nullResult;
}
// Divide
ResultType left = helper(root->left);
ResultType right = helper(root->right);

// Conquer
int singlePath = max(left.singlePath, right.singlePath) + root->val;
singlePath = max(singlePath, 0);

int maxPath = max(left.maxPath, right.maxPath);
maxPath = max(maxPath, left.singlePath + right.singlePath + root->val);

ResultType *result = new ResultType(singlePath, maxPath);
return *result;
}

public:
int maxPathSum(TreeNode *root) {
ResultType result = helper(root);
return result.maxPath;
}
};


### Java

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Result {
int singlePath, maxPath;
Result(int singlePath, int maxPath) {
this.singlePath = singlePath;
this.maxPath = maxPath;
}
}

public class Solution {
public int maxPathSum(TreeNode root) {
return helper(root).maxPath;
}

private Result helper(TreeNode root) {
if (root == null) {
// maxPath should be MIN_VALUE to avoid negtive
return new Result(0, Integer.MIN_VALUE);
}

Result left = helper(root.left);
Result right = helper(root.right);

int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
singlePath = Math.max(0, singlePath); // drop negtive

int maxPath = Math.max(left.maxPath, right.maxPath);
maxPath = Math.max(maxPath, root.val + left.singlePath + right.singlePath);

return new Result(singlePath, maxPath);
}
}


### 源码分析

1. 如果不用 ResultType *XXX = new ResultType ...return *XXX 的方式，则需要在自定义 class 中重载 new operator。
2. 如果遇到 ...private 的编译错误，则是因为自定义 class 中需要把成员声明为 public，否则需要把访问这个成员的函数也做 class 内部处理。