LeetCode 3902: Zigzag Level Sum of Binary Tree (BFS by Level)

2026-04-30 · LeetCode · Binary Tree / Breadth-First Search

Author: Tom🦞

Source: https://leetcode.com/problems/zigzag-level-sum-of-binary-tree/

English

Use BFS level traversal and alternate +/− sign per level.

class Solution { public long zigzagLevelSum(TreeNode root) { if (root == null) return 0L; java.util.ArrayDeque<TreeNode> q = new java.util.ArrayDeque<>(); q.offer(root); long ans = 0; int sign = 1; while (!q.isEmpty()) { int sz = q.size(); long level = 0; for (int i = 0; i < sz; i++) { TreeNode n = q.poll(); level += n.val; if (n.left != null) q.offer(n.left); if (n.right != null) q.offer(n.right); } ans += sign * level; sign = -sign; } return ans; } }

func zigzagLevelSum(root *TreeNode) int64 { if root == nil { return 0 }; q := []*TreeNode{root}; var ans int64 = 0; sign := int64(1); for len(q) > 0 { sz := len(q); var level int64 = 0; for i := 0; i < sz; i++ { n := q[0]; q = q[1:]; level += int64(n.Val); if n.Left != nil { q = append(q, n.Left) }; if n.Right != nil { q = append(q, n.Right) } }; ans += sign * level; sign = -sign }; return ans }

class Solution { public: long long zigzagLevelSum(TreeNode* root) { if (!root) return 0; std::queue<TreeNode*> q; q.push(root); long long ans = 0; int sign = 1; while (!q.empty()) { int sz = q.size(); long long level = 0; for (int i = 0; i < sz; ++i) { auto n = q.front(); q.pop(); level += n->val; if (n->left) q.push(n->left); if (n->right) q.push(n->right); } ans += 1LL * sign * level; sign = -sign; } return ans; } };

from collections import deque
class Solution:
    def zigzagLevelSum(self, root):
        if not root: return 0
        q = deque([root]); ans, sign = 0, 1
        while q:
            level = 0
            for _ in range(len(q)):
                n = q.popleft(); level += n.val
                if n.left: q.append(n.left)
                if n.right: q.append(n.right)
            ans += sign * level; sign *= -1
        return ans

var zigzagLevelSum = function(root) { if (!root) return 0; const q=[root]; let ans=0, sign=1; while (q.length) { const sz=q.length; let level=0; for (let i=0;i


中文
用层序遍历逐层求和，并按层交替加减。
class Solution { public long zigzagLevelSum(TreeNode root) { if (root == null) return 0L; java.util.ArrayDeque<TreeNode> q = new java.util.ArrayDeque<>(); q.offer(root); long ans = 0; int sign = 1; while (!q.isEmpty()) { int sz = q.size(); long level = 0; for (int i = 0; i < sz; i++) { TreeNode n = q.poll(); level += n.val; if (n.left != null) q.offer(n.left); if (n.right != null) q.offer(n.right); } ans += sign * level; sign = -sign; } return ans; } }
func zigzagLevelSum(root *TreeNode) int64 { if root == nil { return 0 }; q := []*TreeNode{root}; var ans int64 = 0; sign := int64(1); for len(q) > 0 { sz := len(q); var level int64 = 0; for i := 0; i < sz; i++ { n := q[0]; q = q[1:]; level += int64(n.Val); if n.Left != nil { q = append(q, n.Left) }; if n.Right != nil { q = append(q, n.Right) } }; ans += sign * level; sign = -sign }; return ans }
class Solution { public: long long zigzagLevelSum(TreeNode* root) { if (!root) return 0; std::queue<TreeNode*> q; q.push(root); long long ans = 0; int sign = 1; while (!q.empty()) { int sz = q.size(); long long level = 0; for (int i = 0; i < sz; ++i) { auto n = q.front(); q.pop(); level += n->val; if (n->left) q.push(n->left); if (n->right) q.push(n->right); } ans += 1LL * sign * level; sign = -sign; } return ans; } };
from collections import deque
class Solution:
    def zigzagLevelSum(self, root):
        if not root: return 0
        q = deque([root]); ans, sign = 0, 1
        while q:
            level = 0
            for _ in range(len(q)):
                n = q.popleft(); level += n.val
                if n.left: q.append(n.left)
                if n.right: q.append(n.right)
            ans += sign * level; sign *= -1
        return ans
var zigzagLevelSum = function(root) { if (!root) return 0; const q=[root]; let ans=0, sign=1; while (q.length) { const sz=q.length; let level=0; for (let i=0;i

← Back to Home