C solution, DFS 6ms with explanation.

• To compute the length of the diameter of the tree, we take the highest value of the sum of the height of the left child + 1 and the height of the right child + 1 for each node.

However, we can avoid making this calculation for somes nodes. If a node has only one child, the diameter of hils child would be the value of the diameter of the current node -1 < current node <= diameter of the tree.

`````` static inline int max(int a, int b) //return the highest value of two int, usefull to compute the hight
{
return a > b? a :b;
}
static int height(struct TreeNode *t)
{
if(!t)
return 0;
return 1 + max(height(t->left), height(t->right));
}

static void dfs(struct TreeNode *root, int *maxi)
{
if(root)
{
if(root->left && !root->right)
dfs(root->left, maxi);
else if(root->right && !root->left)
dfs(root->right, maxi);
else
{
int hei = height(root->left) + height(root->right);
if(hei > *maxi)
*maxi = hei;

dfs(root->left, maxi);
dfs(root->right, maxi);
}
}
}
int diameterOfBinaryTree(struct TreeNode* root)
{
if(!root)
return 0;
int max;
max = height(root->left) + height(root->right);
dfs(root->left, &max);
dfs(root->right, &max);
return max;
}

``````

• you should use a define for the max (as it's valid for any simple type):

``````#define MAX(X,Y) ( ((X)>(Y)) ? (X) : (Y))
``````

• #define MAX(X,Y) ( ((X)>(Y)) ? (X) : (Y))

Haha thank you for the protip.

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