462. Longest Branch Span
A river delta is mapped as a binary tree: each node is a junction, and each child link is a channel flowing from a junction to the next one downstream. A courier wants to travel between two junctions of her choice along channels, visiting no junction twice. She may walk up toward root and then down again, and the route is not required to pass through root.
Return the number of channels (edges) on the longest such route in the tree rooted at root. An empty tree and a tree with a single junction both give 0.
Example 1
- Input:
- root = [6,2,9,1,4,null,10,null,null,3]
- Output:
- 5
- Explanation:
The longest route is 3-4-2-6-9-10, which uses 5 edges.
Example 2
- Input:
- root = [1,null,3,4,5,6,null,null,7]
- Output:
- 4
- Explanation:
The longest route 6-4-3-5-7 uses 4 edges and does not pass through the root.
Constraints
0 ≤ number of nodes in root ≤ 1000
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)