Title:
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.
思路：有点混乱，开始的想法是肯定使用递归，看左右子节点的值，和根值。另外，是求最大值，所以中间就存在最大值，比较左右和根值。但是代码写的很不好。学习好代码
class Solution { public: int maxPathSum(TreeNode *root) { max_sum = INT_MIN; dfs(root); return max_sum; } private: int max_sum; int dfs(const TreeNode *root) { if (root == nullptr) return 0; int l = dfs(root->left); int r = dfs(root->right); int sum = root->val; if (l > 0) sum += l; if (r > 0) sum += r; max_sum = max(max_sum, sum); return max(r, l) > 0 ? max(r, l) + root->val : root->val;//值得学习 } };
LeetCode: Binary Tree Maximum Path Sum
原文：http://www.cnblogs.com/yxzfscg/p/4512026.html