Longest ZigZag Path in a Binary Tree
Medium · Trees · about 20 minutes
Asked at Amazon, Google, Microsoft, Meta.
A ZigZag path starts at any node, picks a direction (left or right) and keeps alternating directions at each step. Its length is the number of nodes visited minus one. Return the longest ZigZag path in the tree.