假设我们找到了一个最优路径，那么该路径上一定存在一个节点，左边的路径是它的左儿子，右边的路径是它的右儿子。所以，只需要在遍历二叉树求路径的同时更新最大值即可。maxPath = max{只保留左边路径，只保留右边路径，同时保留左右两边路径，左右两边路径都不保留（只有节点本身）}，对应第8行无数个max...
代码：
1 int maxPath; 2 3 int maxHalfPathSum(TreeNode *root) { 4 if (!root) 5 return 0; 6 int l = maxHalfPathSum(root->left); 7 int r = maxHalfPathSum(root->right); 8 maxPath = max(maxPath, max(max(max(l, r), l + r), 0) + root->val); 9 return max(max(l, r), 0) + root->val; 10 } 11 12 int maxPathSum(TreeNode *root) { 13 if (!root) 14 return 0; 15 maxPath = root->val; 16 maxHalfPathSum(root); 17 return maxPath; 18 }
Leetcode#124 Binary Tree Maximum Path Sum
原文：http://www.cnblogs.com/boring09/p/4238497.html