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:

     int maxSum=INT_MIN;

     int maxPathSum(TreeNode *root) {

         DFS(root);

         return maxSum;

     }

     int DFS(TreeNode *root)

     {

         if(root==NULL)

         {

             return ;

         }

         int left=DFS(root->left);

         int right=DFS(root->right);

         int sum=root->val;

         if(left>) sum+=left;

         if(right>) sum+=right;

         if(maxSum<sum) maxSum=sum;

         return (left>||right>)?root->val+max(left,right):root->val;

     }

 };