Binary Tree Maximum Path Sum

来源：Leetcode

原帖：https://oj.leetcode.com/problems/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.

代码：

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   // return max singlePath ending with node  
   int maxPathSumHelper(TreeNode *node, int &maxPath) {  
     if (!node) return 0;  
     int l = maxPathSumHelper(node->left, maxPath);  
     int r = maxPathSumHelper(node->right, maxPath);  
     int singlePath = max({node->val, max(l, r) + node->val}); // max (root as node)  
     maxPath = max({maxPath, singlePath, l + r + node->val});  
     return singlePath;  
   }  
   
   int maxPathSum(TreeNode *root) {  
     int maxPath = INT_MIN;  
     maxPathSumHelper(root, maxPath);  
     return maxPath;  
   }  
 };