# My recursive solution and analysis

• class Solution {

public:

``````typedef map<TreeNode*, int> Map;
Map M;

int getMaxFromRoot(TreeNode *root)
{
if(!root)
return 0;
if(M.find(root) != M.end())
return M[root];
int ll = getMaxFromRoot(root->left);
int rr = getMaxFromRoot(root->right);
if(ll < 0)
ll = 0;
if(rr < 0)
rr = 0;
return (M[root] = max(ll, rr) + root->val);
}

int maxPathSum(TreeNode *root) {
if(!root)
return 0;

int ll = root->left ? maxPathSum(root->left) : INT_MIN;  // If no left child, then left-child's max-path-sum is INT_MIN
int rr = root->right ? maxPathSum(root->right) : INT_MIN;
int max_l = getMaxFromRoot(root->left);
int max_r = getMaxFromRoot(root->right);
if(max_l < 0)
max_l = 0;
if(max_r < 0)
max_r = 0;
M[root] = max(max_l, max_r) + root->val;   // M[root]: the max sum of the path that starts from root (root must be included)
return max(max(ll, rr), max_l + max_r + root->val);
}
``````

};

Idea is simple: max-sum path is either in root's left child tree, or root's right child tree, or the path includes root (passes left and right child tree)

• Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.

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