原题
LintCode 94. Binary Tree Maximum Path Sum
Description
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.
解题
题意是找到整棵树中，值最大的一条路径。
对于一个节点而言，值最大的路径其实就等于，左边的节点的值最大路径+右边节点的值最大路径+自己的值（当然前提条件是这些值都大于0，小于0的应该被舍弃）。
那么我们可以维护一个结果值，并从根节点开始寻找值最大路径，只要找到比结果值大的就更新结果值。
代码
/**
* 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) {
// write your code here
if (root == NULL) return 0;
helper(root);
return res;
}
private:
int res = INT_MIN;
int helper(TreeNode *root) {
if (root == NULL) return 0;
int left = helper(root->left);
int right = helper(root->right);
int cur = root->val + max(left, 0) + max(right, 0);
res = max(res, cur);
return root->val + max(left, max(right, 0));
}
};
