Java solution with explanation

• Let us define the diameter of each node as the sum of the longest paths in it's left and right subtrees.
Thus, d = longestPath(left) + longestPath(right)
The diameter of the tree is the max of all such d's

``````public class Solution {
public int diameterOfBinaryTree(TreeNode root) {
Map<TreeNode, Integer> longestPaths = new HashMap<>();
int result = 0;
longestPath(root, longestPaths);
for(TreeNode node : longestPaths.keySet()) {
int d = 0;
if(node.left != null) {
d += (1 + longestPaths.get(node.left));
}
if(node.right != null) {
d += (1 + longestPaths.get(node.right));
}
result = Math.max(result, d);
}

return result;
}

private int longestPath(TreeNode node, Map<TreeNode, Integer> longestPaths) {
if(node == null) {
return -1;
}

int result = Math.max(1 + longestPath(node.left, longestPaths), 1 + longestPath(node.right, longestPaths));
longestPaths.put(node, result);

return result;
}
}
``````

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