Diameter of Binary Tree
Find the length, in edges, of the longest path between any two nodes in a binary tree.
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree 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 measured by the number of edges between the two nodes.
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], with length 3.
Example 2
Input: root = [1,2]
Output: 1
Example 3
Input: root = []
Output: 0
Constraints
- The number of nodes in the tree is in the range [0, 10^4].
- -100 <= Node.val <= 100
Follow-up
Can you compute the diameter in a single DFS pass without recomputing height at every node?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.