LC1372 Longest ZigZag Path in a Binary Tree 🟡
Carry direction + length — continue when you match the expected turn, reset when you don't. Length counts edges.
You are given the root of a binary tree.
A ZigZag path for a binary tree is defined as follows:
- Choose any node in the binary tree and a direction (right or left).
- If the current direction is right, move to the right child; otherwise move to the left child.
- Change the direction from right to left or from left to right.
- Repeat until you can't move in the tree.
Zigzag length is defined as the number of nodes visited − 1. (A single node has length 0.)
Return the longest ZigZag path contained in that tree.
- Input:
- root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
- Output:
- 3
- Explanation:
- Longest zigzag: right → left → right — 3 edges.
- Input:
- root = [1,1,1,null,1,null,null,1,1,null,1]
- Output:
- 4
- Explanation:
- Longest zigzag: left → right → left → right — 4 edges.
- Input:
- root = [1]
- Output:
- 0
- Explanation:
- Single node — length 0.
- The number of nodes is in the range [1, 5 * 10^4].
- 1 <= Node.val <= 100
Full solution · Try yourself firstพับไว้ด้านใน — คลิกเมื่อพร้อมดู
Top-down with state — the state is the expected next direction plus the length so far.
1. Mindset Shift
The best zigzag can start anywhere and in either direction.
Key insight: carry go_left and length. Match the plan → length+1 and flip direction. Mismatch → restart at length 1.
2. The Logic — 5 Steps
- ans = 0
- dfs(node, go_left, length): return if None
- Update ans at every visited node
- If go_left: continue left (length+1, next expects right) and restart right at 1
- Symmetric for go_left=False · call from root twice with length 0
3. LeetCode-Ready Code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestZigZag(self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(node, go_left, length):
nonlocal ans
if node is None:
return
ans = max(ans, length)
if go_left:
dfs(node.left, False, length + 1)
dfs(node.right, True, 1)
else:
dfs(node.right, True, length + 1)
dfs(node.left, False, 1)
dfs(root, True, 0)
dfs(root, False, 0)
return ans4. Dry Run — right → left → right
| step | expected | actual | length | ans |
|---|---|---|---|---|
| at root | go right | has right child | 0 → 1 | 1 |
| at right | go left | has left child | 1 → 2 | 2 |
| at left | go right | has right child | 2 → 3 | 3 |
| next | go left | dead end | stop | 3 |
5. Edge Cases & Pitfalls
- Length counts edges, not nodes — start at 0 on the root
- Update ans at every node, not only at path ends
6. Time & Space Complexity
- Time O(n) — visit every node once
- Space O(h) — call-stack depth
When a path has alternating state (direction, color, up/down), pass that state into DFS and reset length when the state breaks.