Given the root of a binary tree, return the length (number of edges) of the longest path between any two nodes in the tree. The path may or may not pass through the root.
Example 1
Input: root = [1,2,3,4,5]
Output: 3
Explanation: The longest path is 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3), 3 edges.
The number of nodes is in the range [1, 10^4]The diameter through any single node equals the sum of its left and right subtree HEIGHTS — but the overall answer might come from a node that isn't the root.
You need to compute height anyway (recursively) — the trick is updating a running 'best diameter seen so far' as a side effect of that same height computation, rather than a separate pass.
Don't recompute height from scratch at every node (that's O(n^2)) — compute it bottom-up once, and the diameter check piggybacks on the same traversal.
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
height(root);
return maxDiameter;
}
private int height(TreeNode node) {
if (node == null) return 0;
int leftHeight = height(node.left);
int rightHeight = height(node.right);
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight); // diameter THROUGH this node
return 1 + Math.max(leftHeight, rightHeight); // height, returned normally to the caller
}Time: O(n) · Space: O(h)