#1372
Longest ZigZag Path in a Binary Tree
specialist · 600 · lc medium +29 · verified · 67% accepted · 3,743 likes · top 73%
Description
You are given the root of a binary tree.
A ZigZag path begins at any node and alternates direction at every step: if the previous move was to a right child, the next must go to a left child, and vice versa. The path's length is its number of edges (nodes visited minus one; a single node has length 0).
Return the length of the longest ZigZag path in the tree.
Example 1:
Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
Example 2:
Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
Example 3:
Input: root = [1]
Output: 0
Code
1
2
3
4
5
6
7
8
9