The problem
The diameter of a binary tree is the length of the longest path between any two nodes, counted in edges (the links between nodes). The path does not have to pass through the root.
Given the root, return the diameter.
Examples
01
- Input
root = [1, 2, 3, 4, 5]
- Output
3
02
- Input
root = [1, 2]
- Output
1
Constraints
- 1 ≤ number of nodes ≤ 10⁴
- −100 ≤ Node.val ≤ 100
The idea
Every path has one highest node, where it bends: it goes down the left side and down the right. At a node, the longest path bending there is the height of its left subtree plus the height of its right.
So compute heights bottom-up (as in Maximum Depth), and at each node, while its two heights are in hand, record left + right if it beats the best so far. One pass finds the answer.
- Time
- O(n)
- Space
- O(h)
Solution · every language run against every case
class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: best = 0 def height(node): # edges on the longest path down from node, plus one nonlocal best if not node: return 0 left, right = height(node.left), height(node.right) best = max(best, left + right) # the longest path that bends at node return 1 + max(left, right) height(root) return best