Diameter of Binary Tree
EasyTrees
Given the root of a binary tree, return the length of its *diameter*.
The diameter is the length of the longest path between any two nodes in the tree, measured as the number of edges on the path (not the number of nodes). The path does not have to pass through the root. A tree with one node has diameter 0.
Trees are written in level order: values are listed level by level, left to right, and null marks a missing child (trailing nulls are omitted).
Example 1
- Input:
- root = [1,2,null,3,4,5,null,6]
- Output:
- 4
- Explanation
- The longest path runs from the leaf 5 up through 3 and 2 and down through 4 to the leaf 6, which is 4 edges. It never touches the root.
Example 2
- Input:
- root = [1,2,3,4,null,null,5]
- Output:
- 4
- Explanation
- Here the longest path does go through the root: 4 → 2 → 1 → 3 → 5, which has 4 edges.
Example 3
- Input:
- root = [1,2,null,3]
- Output:
- 2
- Explanation
- The only long path runs from 3 up to the root, which is 2 edges. Counting edges rather than nodes is why the answer is 2 and not 3.
Constraints
- The number of nodes is in the range
[1, 10^4] -100 <= Node.val <= 100- The tree height is at most
500