619. Longest ZigZag Path in a Binary Tree
A zigzag path in a binary tree is built like this: pick any node and a first direction (left or right), step to that child, then keep stepping while flipping the direction every time — left, right, left, right, … The path ends as soon as the required child doesn't exist. Its length is the number of edges used, so a path that never leaves its starting node has length 0.
The function receives root, the root of the tree, and returns the length of the longest zigzag path found anywhere in it. The path does not need to pass through the root.
Example 1:
Input: root = [5, 3, 8, null, 6, null, 9, 7]
Output: 3
Explanation: Start at the root: 5 → 3 (left), 3 → 6 (right), 6 → 7 (left). Directions alternate L, R, L across 3 edges, and no longer zigzag exists.
Example 2:
Input: root = [1, null, 2, null, 3]
Output: 1
Explanation: The tree is a straight right-right chain. Two consecutive right moves never alternate, so the best zigzag is any single edge: length 1.
Constraints:
- The number of nodes is in the range [1, 5 * 10⁴]
- 1 ≤ Node.val ≤ 100
Hints:
Once a starting node and a first direction are fixed, the whole zigzag is forced — each step has exactly one legal child. That gives a correct but slow plan: walk the forced path from every node.
Think bottom-up instead. For each node keep two numbers: the longest zigzag that starts here by going left, and the one that starts by going right.
The recurrence flips direction at the child: goLeft(node) = 1 + goRight(node.left), and goRight(node) = 1 + goLeft(node.right). One post-order DFS computes every pair and a running maximum.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [5, 3, 8, null, 6, null, 9, 7]
Expected output: 3