class Solution {
public:
int maxPathSum(TreeNode *root) {
buildVector(root);
return maxVal;
}
int buildVector(TreeNode *root){
if(!root)
return 0;
int left = buildVector(root>left);
int right = buildVector(root>right);
//assume this node as root and calcu maxVal based on it
int sum = root>val;
if(left > 0)
sum += left;
if(right > 0)
sum += right;
if(sum > maxVal)
maxVal = sum;
//return val is either left or right node with this node
left = left > right ? left : right;
sum = root>val;
if(left > 0)
sum += left;
return sum;
}
private:
int maxVal = INT_MIN;
};
Simple and easy understood recursive c++ code with O(n) time


understand why such recurstion lsum, rsum and result is passed with pointer here at with same code and same example : http://goo.gl/wuatmP