Diameter of Binary Tree

easy

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The length of a path is the number of edges between the nodes.

Test Cases

Copy an input into the main harness and Run to verify

Input

root = [1,2,3,4,5]

Expected Output

3

Explanation: The longest path is [4,2,1,3] or [5,2,1,3], which has 3 edges.

Input

root = [1,2]

Expected Output

1

Constraints

The number of nodes in the tree is in the range [1, 10^4].
-100 <= Node.val <= 100

Hints

Hint 1 — click to reveal

For any node, the longest path *through* it is leftHeight + rightHeight edges.

Hint 2 — click to reveal

Compute heights once in a post-order pass and update a running best along the way.

Java Compiler