Binary Tree Zigzag Path Collector
Problem Description
Given the root of a binary tree, collect all root-to-leaf paths. Return the list of paths where:
- **Odd-depth nodes** (root is depth 1, so root itself and every other level) contribute their value normally.
- **Even-depth nodes** contribute the **negation** of their value (i.e., `–node.val`).
Each path is returned as the **sum** of the transformed node values along that path. Return all such path sums in any order.
**Example 1:**
```
Input: root = [1, 2, 3, 4, 5]
Tree:
1
/ \
2 3
/ \
4 5
Depth assignments: 1→depth1(odd), 2→depth2(even), 3→depth2(even), 4→depth3(odd), 5→depth3(odd)
Paths and sums:
- 1 → 2 → 4: 1 + (-2) + 4 = 3
- 1 → 2 → 5: 1 + (-2) + 5 = 4
- 1 → 3: 1 + (-3) = -2
Output: [3, 4, -2] (any order)
```
**Example 2:**
```
Input: root = [7, 9, null, 6, null]
Tree:
7
/
9
/
6
Depths: 7→1(odd), 9→2(even), 6→3(odd)
Path: 7 → 9 → 6: 7 + (-9) + 6 = 4
Output: [4]
```
**Constraints:**
- The number of nodes is in the range `[1, 1000]`.
- `-500 <= Node.val <= 500`
Constraints
- 1 <= number of nodes <= 1000
- -500 <= Node.val <= 500
Follow-up
Instead of alternating signs by depth, use an alternating sign that flips at each *node* rather than each level, and collect only paths whose sum equals a given target.
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.