```
// To search the maximum branch rooted at Node root, and also update the maxPath, which is the currently founded max path
int maxBranchSearch(TreeNode *root, int &maxPath){
int maxL, maxR;
if(!root)
{// if a empty tree, then the maximum branch is 0
return 0;
}
else
{
maxL = max(maxBranchSearch(root->left, maxPath), 0); // find the maximum branch rooted at root->left, it can be empty (0)
maxR = max(maxBranchSearch(root->right, maxPath),0);// find the maximum branch rooted at root->right, it can be empty (0)
maxPath = max(maxPath, maxL + root->val + maxR); // update the maximum path, it is either the old one, or a one passing through root
return max(maxL, maxR) + root->val; // the maximum branch rooted at root is either root + max_branch of left/right, or root itself
}
}
int maxPathSum(TreeNode *root) {
int maxPath = INT_MIN;
maxBranchSearch(root, maxPath);
return maxPath;
}
```