Binary Tree Maximum Path Sum (C++ code)

LeetCode Binary Tree Maximum Path Sum, Nov 8 '12
难度4，出现频率2
  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.
思路： recursion,在当前node, 设定函数返回包含当前node最长单向path，最大和可能是：
1，当前node + 左边最长单向(if >0) +右边最长单向(if >0)
2, 从左边node开始的最大和
3，从右边node开始的最大和
所以函数要返回的是包括当前node的最长单向和，同时在主体里更新最大和。

int maxDirected(TreeNode *root, int &maxSofar){
   if(!root) return 0;   
   int leftmax = maxDirected(root->left, maxSofar);
   int rightmax = maxDirected(root->right, maxSofar);
   int temp = root->val;
   temp = temp + max(leftmax,0) + max(rightmax,0); //temp is the max sum containing root;
   maxSofar = max(maxSofar, temp);

   int directedSum =  max(leftmax, rightmax );
  directedSum = root->val +max(directedSum,0);

   return directedSum ;
}

int maxPathSum(TreeNode *root){
   if(!root) return INT_MIN;
   int maxSofar = root->val ;
  
  maxDirected(root, maxSofar);

  return maxSofar;
}