For more info, please refer to my blog post.

```
class Solution {
public:
int maxPathSum(TreeNode *root) {
int height, diameter;
treeHeightDiameter(root, height, diameter);
return diameter;
}
/**
* divide & conquer: two farthest nodes are such that
* 0) root is in the path
* root is not, two cases
* 1) both in the left tree
* 2) right
*/
// @param height: longest distance from a node to root, including root itself; not necessarily a leaf bcoz val can be negative
// @param diameter: longest distance between two nodes in the tree
void treeHeightDiameter(TreeNode *root, int &height, int &diameter) {
int l_height = -10000;
int l_diameter = -10000;
int r_height = -10000;
int r_diameter = -100000;
if (!root) {
height = 0;
diameter = 0;
return;
}
if (!root->left && !root->right) {
height = root->val;
diameter = root->val;
return;
}
if (root->left)
treeHeightDiameter(root->left, l_height, l_diameter);
if (root->right)
treeHeightDiameter(root->right, r_height, r_diameter);
height = max(l_height, r_height);
height = (height > 0) ? (height + root->val) : root->val;
diameter = root->val;
if (l_height > 0)
diameter += l_height;
if (r_height > 0)
diameter += r_height;
diameter = max(diameter, l_diameter);
diameter = max(diameter, r_diameter);
}
};
```