[LeetCode]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. or 2 / -1 Return 2.

这道题是返回二叉树中任意两点路径的最大值，只要两点之间路径相同就可以了。那道题想到的就是用递归，但是一开始总是wrong answer，后来才发现傻缺了，递归的返回值和路径的最大和是两个概念，返回值不能够是最大和啊！！！ 下面贴上代码：

/** * 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 fun(TreeNode* root,int& sum){if (root == NULL)return 0;int left = max(fun(root->left,sum),0);int right = max(fun(root->right,sum),0);sum = max(sum, left + right + root->val);return max(left + root->val, right + root->val);}int maxPathSum(TreeNode* root){int sum = INT_MIN;fun(root,sum);return sum;}};

，这个社会是存在不公平的，不要抱怨，因为没有用！人总是在反省中进步的！