# 29ms C++ recursive solution, beats 98%

• In my example, `monoPath` refers to right/left path plus root while `dualPath` refers to the path that formed by both right and left and root.

`````` * Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPath(TreeNode* root, TreeNode* parent, int& result) {
if (root == NULL) {
return INT_MIN;
}
else if (root -> left == NULL && root -> right == NULL) {
result = max(result,root->val);
return root -> val;
}
else {
int leftPath = INT_MIN, rightPath = INT_MIN;
if (root -> left != NULL) {
leftPath = maxPath(root -> left, root, result);
}
if (root -> right != NULL) {
rightPath = maxPath(root -> right, root, result);
}

int maxSubPath = max(leftPath, rightPath), monoPath = 0, dualPath = 0;
monoPath = maxSubPath < 0 ? root -> val : root -> val + maxSubPath;

if (leftPath < 0) leftPath = 0;
if (rightPath < 0) rightPath = 0;
dualPath = leftPath + rightPath + root -> val;
result = max(result, max(monoPath, dualPath));

return parent ? monoPath : dualPath;
}
}
int maxPathSum(TreeNode* root) {
int result = INT_MIN;
maxPath(root, NULL, result);
return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.