A downward path in a binary tree is a sequence of moves from a node to one of its children; each move goes either left or right. A turn happens whenever a left move is directly followed by a right move or vice versa. Moves in the same direction in a row do not count as turns. A downward path may start at any node and end at any node below it. Return the largest number of turns of any downward path (0 for an empty tree or when no path turns).
Examples
1
/
2
/ \
3 4
\
5
/
6
Input: root = build_tree([1, 2, None, 3, 4, None, None, None, 5, 6])
Output: 2
Explanation: 1 -> 2 (left) -> 4 (right) -> 5 (right) -> 6 (left) turns twice.
Input: root = build_tree([1, 2, 3, 4, 5, 6, 7])
Output: 1
Constraints
0 <= number of nodes <= 1000
Goals
- Track two states per node depending on the direction of the last move
- Combine 'extend straight', 'turn' and 'start fresh' at every child