493. Longest Zigzag Route
A delivery robot may start at any node of a road network shaped like a binary tree whose top node is root. It first picks a starting direction, left or right, and moves to that child. After that, every move must switch direction: after stepping to a left child, the next step goes to the right child of the current node, and after stepping to a right child, the next step goes to a left child. The robot may stop whenever it likes, or when the required child does not exist.
The length of a route is the number of moves it makes. Return the greatest possible length over all starting nodes and starting directions. A tree with a single node or no node has answer 0.
Example 1
- Input:
- root = [2,5,9,null,7,null,4,3,null,null,8]
- Output:
- 3
- Explanation:
The route 2 -> 5 (left) -> 7 (right) -> 3 (left) makes 3 moves, and no route is longer.
Example 2
- Input:
- root = [1,2,3]
- Output:
- 1
- Explanation:
The route 6 -> 4 (left) -> 8 (right) has 2 moves, as does 6 -> 7 (right) -> 5 (left); nothing reaches 3.
Constraints
0 ≤ number of nodes ≤ 105
0 ≤ Node.val ≤ 100
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)