Longest ZigZag Path in a Binary Tree

Given the root of a binary tree, return the length of the longest ZigZag path. A ZigZag path alternates between left and right child choices at each step. Pattern focus: Tree DP. Keep track of the best path when you arrive from the left and when you arrive from the right.

Input Format

root = binary tree in level-order array form

Output Format

length of the longest ZigZag path

Constraints

  • 0 <= number of nodes <= 10^5
  • node values can be any integers
  • Tree is given in level-order form with nulls

Examples

Example 1:

Input:

root = [1,null,1,1,1,null,null,1,1,null,1]

Output:

3

Explanation:

The longest alternating path contains 3 edges.

Example 2:

Input:

root = [1,2,3]

Output:

1

Explanation:

Any single edge forms a ZigZag of length 1.

Example 3:

Input:

root = [1]

Output:

0

Explanation:

A single node has no edges.

Loading...
Longest ZigZag Path in a Binary Tree