LintCode (94) Binary Tree Max Sum

Given a binary tree, find the maximum path sum.

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

Have you met this question in a real interview? 

Yes

Example

Given the below binary tree:

  1
 / \
2   3

return 6.

凡是traverse带参数的都是夹带私活的。。。这个的私活是，中间还要连起来，维护一个最大值作为参数。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/** * 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) return 0; myMax=INT_MIN; maxHelper(root); return myMax; } int maxHelper(TreeNode* root){ if (!root) return 0; int l=max(0, maxHelper(root->left)); int r=max(0, maxHelper(root->right)); myMax=max(myMax, l+r+root->val); return max(l,r)+root->val; } int myMax; };