Skip to main content

Binary Tree Zigzag Path Collector

medium
Binary TreeTreeDepth First SearchDfs Recursive
Asked atAmazonGoogleBloomberg

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.