T******7
发帖数: 1419 | 1 //==========================================================================
==
// 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.
//
//==========================================================================
==
#include
using namespace std;
/**
* 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)
{
if (root == NULL) return 0;
int maxSoFar = root->val;
maxPathSumHelper(root, maxSoFar);
return maxSoFar;
}
int maxPathSumHelper(TreeNode *node, int &maxSoFar)
{
if (node == NULL) return 0;
int leftMax = maxPathSumHelper(node->left, maxSoFar);
int rightMax = maxPathSumHelper(node->right, maxSoFar);
int maxPath = node->val;
if (leftMax > 0) maxPath += leftMax;
if (rightMax > 0) maxPath += rightMax;
if (maxPath > maxSoFar) maxSoFar = maxPath;
int res = node->val;
return max(res, res+max(leftMax, rightMax));
}
};
int main()
{
return 0;
} | Y**3
发帖数: 21 | | p*g
发帖数: 141 | 3 为什么不自己试试能不能过leetcode 的OJ
我当时调试了一阵， 最终过了
如果你fail了几个case，那很可能你的算法有地方有问题
==
【在 T******7 的大作中提到】
: //==========================================================================
: ==
: // 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,
: //
| n******e
发帖数: 957 | | P******r
发帖数: 842 | |
|
