# An intuitive divide-and-conquer solution

``````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);
}
};
``````

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