The diameter of a binary tree is the number of edges on the longest path between any two nodes. That path may or may not pass through the root.
Given the root of a binary tree, return its diameter.
Examples
1
/ \
2 3
/ \
4 5
Input: root = [1, 2, 3, 4, 5]
Output: 3
Explanation: The path 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3) has 3 edges.
1
/
2
Input: root = [1, 2]
Output: 1
Input: root = [1]
Output: 0
Constraints
1 <= number of nodes <= 1000
Goals
- Write a helper that returns one value (height) while updating another (best answer) as a side effect
- Use nonlocal or an instance attribute to share state with a nested function
- Recognise that the answer may not pass through the root