1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    /**
18     * Performs a level-order (BFS) traversal of the binary tree and
19     * computes the sum of node values on each level.
20     *
21     * Note: Since addition is commutative, the "zigzag" direction does
22     * not change a level's sum. The result is therefore identical to a
23     * plain level-sum traversal; the zigzag aspect only matters if the
24     * order of elements within a level needs to be preserved.
25     *
26     * @param root the root of the binary tree
27     * @return a list where the i-th element is the sum of values at level i
28     */
29    public List<Long> zigzagLevelSum(TreeNode root) {
30        List<Long> answer = new ArrayList<>();
31
32        // Guard against an empty tree.
33        if (root == null) {
34            return answer;
35        }
36
37        // Queue holding all nodes belonging to the current level.
38        Deque<TreeNode> queue = new ArrayDeque<>();
39        queue.offer(root);
40
41        while (!queue.isEmpty()) {
42            int levelSize = queue.size();
43            long levelSum = 0L;
44
45            // Process exactly the nodes that make up this level.
46            for (int i = 0; i < levelSize; i++) {
47                TreeNode node = queue.poll();
48                levelSum += node.val;
49
50                // Enqueue children so they form the next level.
51                if (node.left != null) {
52                    queue.offer(node.left);
53                }
54                if (node.right != null) {
55                    queue.offer(node.right);
56                }
57            }
58
59            answer.add(levelSum);
60        }
61
62        return answer;
63    }
64}
65```
66
67### Key improvements
68
69| Aspect | Original | Rewritten |
70|--------|----------|-----------|
71| **Correctness** | Could break early and miss values | Always sums every node on the level |
72| **Null safety** | Would `NullPointerException` on empty tree | Returns empty list for `null` root |
73| **Data structure** | `ArrayList` rebuilt each level | Single `ArrayDeque` queue (idiomatic BFS) |
74| **Clarity** | Confusing zigzag indexing irrelevant to a sum | Straightforward level grouping via `levelSize` |
75| **Memory** | Allocates a new list per level | Reuses one queue |
76
77### Alternative perspective
78
79If you genuinely need the elements ordered in zigzag fashion (left-to-right, then right-to-left) — for example to build the level lists themselves rather than a sum — you would track a `leftToRight` flag and use `addFirst`/`addLast` on a `LinkedList` per level. But for a pure **sum**, the direction is irrelevant, so the cleaner approach above is preferred.
80
81Required imports for this solution:
82
83```java
84import java.util.ArrayDeque;
85import java.util.ArrayList;
86import java.util.Deque;
87import java.util.List;
88

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    vector<long long> zigzagLevelSum(TreeNode* root) {
15        vector<long long> ans;
16        if (root == nullptr) {
17            return ans;
18        }
19
20        // Use a queue to perform a standard breadth-first (level-order) traversal.
21        // Since we only need the sum of each level, the left-to-right vs.
22        // right-to-left "zigzag" order does not change the result of the sum.
23        queue<TreeNode*> q;
24        q.push(root);
25
26        while (!q.empty()) {
27            int levelSize = q.size();   // Number of nodes on the current level.
28            long long levelSum = 0;     // Accumulated sum for the current level.
29
30            // Process exactly the nodes belonging to the current level.
31            for (int i = 0; i < levelSize; ++i) {
32                TreeNode* node = q.front();
33                q.pop();
34
35                levelSum += node->val;
36
37                // Enqueue children to be processed on the next level.
38                if (node->left != nullptr) {
39                    q.push(node->left);
40                }
41                if (node->right != nullptr) {
42                    q.push(node->right);
43                }
44            }
45
46            ans.push_back(levelSum);
47        }
48
49        return ans;
50    }
51};
52```
53
54### Key improvements
55
561. **Correctness fix** — The original code had two bugs:
57   - The `break` statement stopped summing a level the moment it encountered a node whose relevant child was null, dropping legitimate node values from the sum.
58   - The `left`/`right` zigzag branching was irrelevant for a sum, which is commutative.
59
602. **Standard idiom** — Using `std::queue<TreeNode*>` instead of two `std::vector` buffers makes the BFS intent explicit and idiomatic.
61
623. **Null-root guard** — Added an early return so an empty tree yields an empty result instead of dereferencing a null pointer.
63
644. **Naming** — `levelSize` and `levelSum` describe purpose more clearly than `m` and `s`, while the method name `zigzagLevelSum` is preserved as required.
65
66### Alternative perspective
67
68If you specifically want to **preserve the two-vector BFS structure** (no `std::queue`), here is a minimal correction of the original approach:
69
70```cpp
71class Solution {
72public:
73    vector<long long> zigzagLevelSum(TreeNode* root) {
74        vector<long long> ans;
75        if (root == nullptr) {
76            return ans;
77        }
78
79        vector<TreeNode*> currentLevel = {root};
80        while (!currentLevel.empty()) {
81            vector<TreeNode*> nextLevel;
82            long long levelSum = 0;
83
84            for (TreeNode* node : currentLevel) {
85                levelSum += node->val;            // Sum every node on this level.
86                if (node->left != nullptr) {
87                    nextLevel.push_back(node->left);
88                }
89                if (node->right != nullptr) {
90                    nextLevel.push_back(node->right);
91                }
92            }
93
94            ans.push_back(levelSum);
95            currentLevel = std::move(nextLevel);  // Advance to the next level.
96        }
97
98        return ans;
99    }
100};
101

1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 *     val: number
5 *     left: TreeNode | null
6 *     right: TreeNode | null
7 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 *         this.val = (val===undefined ? 0 : val)
9 *         this.left = (left===undefined ? null : left)
10 *         this.right = (right===undefined ? null : right)
11 *     }
12 * }
13 */
14
15/**
16 * Computes the sum of node values for each level of a binary tree.
17 *
18 * A queue-based BFS is used to traverse the tree level by level. The
19 * `leftToRight` flag tracks the zigzag direction; while it does not affect
20 * the numeric sum of a level, it is preserved here to reflect the original
21 * zigzag traversal intent.
22 *
23 * @param root The root node of the binary tree, or null for an empty tree.
24 * @returns An array where each element is the sum of node values on that level.
25 */
26function zigzagLevelSum(root: TreeNode | null): number[] {
27    const result: number[] = [];
28
29    // Guard against an empty tree.
30    if (root === null) {
31        return result;
32    }
33
34    // Initialize the BFS queue with the root node.
35    let queue: TreeNode[] = [root];
36
37    // Tracks the current zigzag direction (left-to-right vs. right-to-left).
38    let leftToRight = true;
39
40    while (queue.length > 0) {
41        // Collects all child nodes for the next level.
42        const nextQueue: TreeNode[] = [];
43
44        // Accumulates the sum of values for the current level.
45        let levelSum = 0;
46
47        const levelSize = queue.length;
48
49        for (let i = 0; i < levelSize; i++) {
50            // Select the node according to the current zigzag direction.
51            const node = leftToRight ? queue[i] : queue[levelSize - i - 1];
52
53            // Add this node's value to the running level sum.
54            levelSum += node.val;
55        }
56
57        // Enqueue children in natural (left-to-right) order for the next level.
58        for (const node of queue) {
59            if (node.left !== null) {
60                nextQueue.push(node.left);
61            }
62            if (node.right !== null) {
63                nextQueue.push(node.right);
64            }
65        }
66
67        result.push(levelSum);
68
69        // Flip the direction for the next level.
70        leftToRight = !leftToRight;
71
72        // Advance to the next level.
73        queue = nextQueue;
74    }
75
76    return result;
77}
78```
79
80**Key changes and reasoning:**
81
821. **Fixed the shadowing bug** — Replaced the destructured `for (const { left, right } of q)` with `for (const node of queue)`, so the outer direction flag (renamed `leftToRight`) is no longer overwritten.
83
842. **Renamed variables for clarity** — `q` → `queue`, `nq` → `nextQueue`, `m` → `levelSize`, `s` → `levelSum`, `ans` → `result`, `left` → `leftToRight`.
85
863. **Added a null guard** — Prevents `null` from entering the queue, which would otherwise cause runtime errors when accessing `.val`, `.left`, `.right`.
87
884. **Corrected the sum logic** — Removed the premature `break` tied to a child's existence. A level sum should include every node on that level regardless of whether it has children.
89
90**Alternative perspective:** Since summing a level is order-independent, the `leftToRight` flag and the conditional node selection are functionally redundant for the *sum* result. If the goal is purely the per-level sum, you could drop the direction logic entirely and simply iterate the queue. I retained it above to honor the original "zigzag" naming and structure, but here is the streamlined variant if the zigzag aspect is unnecessary:
91
92```typescript
93function zigzagLevelSum(root: TreeNode | null): number[] {
94    const result: number[] = [];
95    if (root === null) {
96        return result;
97    }
98
99    let queue: TreeNode[] = [root];
100    while (queue.length > 0) {
101        const nextQueue: TreeNode[] = [];
102        let levelSum = 0;
103
104        for (const node of queue) {
105            levelSum += node.val;
106            if (node.left !== null) {
107                nextQueue.push(node.left);
108            }
109            if (node.right !== null) {
110                nextQueue.push(node.right);
111            }
112        }
113
114        result.push(levelSum);
115        queue = nextQueue;
116    }
117
118    return result;
119}
120