Zigzag Tree Descent

Medium

You are given the root of a binary tree. A *zigzag descent* starts at any node: pick a direction (left or right) and move to that child, then switch to the opposite direction and move again, and so on, until the required child is missing. The length of a descent is the number of steps taken (a single node with no steps has length 0). Return the greatest zigzag descent length in this tree.

Example 1

root=tree_node([4, 2, 9, None, 7, None, None, 5, None, None, 1]) → 4

From the root 4 go left to 2, right to 7, left to 5, right to 1: four steps, switching direction every time.

Example 2

root=tree_node([1, None, 2, None, 3]) → 1

The tree is a right-only chain, so there is nowhere to turn and the descent lasts one step.

Example 3

root=tree_node([8]) → 0

A single node gives a descent of zero steps.

Constraints

1 ≤ number of nodes ≤ 5 · 10⁴
The depth of the tree is at most 900
1 ≤ Node.val ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Dynamic Programming Binary Tree

Similar problems

Biggest Search Subtree Medium A Party Without Direct Bosses Medium Heaviest Path in a Tree Hard Fewest Guards on a Tree Hard Heaviest Search Subtree Hard

Input

root=tree_node([4, 2, 9, None, 7, None, None, 5, None, None, 1])

Expected

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.