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.
public int diameterOfBinaryTreeBruteForce(TreeNode root) {
if (root == null) return 0;
int throughRoot = height(root.left) + height(root.right);
int bestInLeft = diameterOfBinaryTreeBruteForce(root.left);
int bestInRight = diameterOfBinaryTreeBruteForce(root.right);
return Math.max(throughRoot, Math.max(bestInLeft, bestInRight));
}
private int height(TreeNode node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}Time: O(n^2) worst case · Space: O(h)