You get the root of a binary tree. Any two of its nodes are joined by exactly one path along the tree's edges. The diameter is the length of the longest such path, counted in edges (not nodes).
Return the diameter. The longest path can run between any two nodes, so it doesn't have to pass through the root.
The path 4 → 6 → 3 → 8 → 10 → 14 uses 5 edges, and no pair of nodes is farther apart. (7 → 6 → 3 → 8 → 10 → 14 ties it.)
The path 5 → 3 → 2 → 4 → 6 has 4 edges. Any path through the root 1 has at most 3.
A single node is a path with no edges.
Constraints
1 and 10⁴ nodes.-100 <= Node.val <= 100Every path has one highest node, where it turns from going up to going down. Through a given node, the longest path runs down its deepest left branch and its deepest right branch.
Pick any path in the tree and look at its highest node. The path climbs up to that node from one side and goes back down the other side. Every path has exactly one such turning point (a path that only goes down turns at its top end, with nothing on one side).
Time O(n)Space O(h)
The full walkthrough and code are part of Premium
5