Leetcode#124 Binary Tree Maximum Path Sum

假设我们找到了一个最优路径，那么该路径上一定存在一个节点，左边的路径是它的左儿子，右边的路径是它的右儿子。所以，只需要在遍历二叉树求路径的同时更新最大值即可。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 }