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.
思想： 后序遍历。注意路径的连通： 结点不为空时要返回 max( max(leftV, rightV)+rootV, rootV);
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode *root) {
getMaxSum(root);
return _maxPathSum;
}
protected:
int getMaxSum(TreeNode *root) {
if(root == NULL) return Min_Val;
int left = getMaxSum(root->left);
int right = getMaxSum(root->right);
return findMax(left, right, root->val);
}
int findMax(int left, int right, int rootV) {
int PathSum = max(max(left, right)+rootV, rootV);
_maxPathSum = max(_maxPathSum, max(PathSum, rootV + left + right));
return PathSum;
}
private:
enum{ Min_Val = -1000};
int _maxPathSum = Min_Val;
};