题目
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
分析
给定一颗二叉树，求其最大路径和。对于二叉树，算法大多可以选择递归解决，此题也不例外。
如果只是一个节点,那么当然就是这个节点的值了.
如果这个作为root,那么最长路应该就是..
F(left) + F(right) + val...当然如果left,或者right<0就不用加了的= =
从下往上递归遍历...
如果不这个不是root,那么就不能把left和right加起来了...因为只是一条路...
AC代码
/**
* 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 maxVal = INT_MIN;
int maxPathSum(TreeNode* root) {
if (root == NULL)
return ; maxSum(root);
return maxVal;
} /*递归函数*/
int maxSum(TreeNode *root)
{
if (root == NULL)
return ; /*求以root为根的当前子树的最大路径和*/
int curVal = root->val;
int lmaxSum = maxSum(root->left), rmaxSum = maxSum(root->right);
if (lmaxSum > )
curVal += lmaxSum;
if (rmaxSum > )
curVal += rmaxSum; if (curVal > maxVal)
maxVal = curVal; /*返回以当前root为根的子树的最大路径和*/
return max(root->val, max(root->val + lmaxSum, root->val + rmaxSum));
}
};