class Solution {
int res;
public:
int depth(TreeNode *root){
if(root==NULL) return 0;
int a=depth(root>left), b=depth(root>right);
res=max(res,a+b+root>val);//if *root is the top node in the path
return max(0,max(a, b)+root>val);//if *root is in the path, if this branch a burden or a plus
}
int maxPathSum(TreeNode *root) {
if(root==NULL) return 0;
res=root>val;
depth(root);
return res;
}
};
Clean c++ solution


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

the res as a parameter is better:
class Solution { public: int maxPathSum(TreeNode* root) { if(!root) return 0; int res = root>val; depth(root, res); return res; } private: int depth(TreeNode* root, int& res) { if(!root) return 0; int a = depth(root>left, res), b = depth(root>right, res); res = max(res, a+b+root>val); return max(0, max(a, b)+root>val); } };