Skip to content

3902. Zigzag Level Sum of Binary Tree πŸ”’

Description

You are given the root of a binary tree.

Traverse the tree level by level using a zigzag pattern:

  • At odd-numbered levels (1-indexed), traverse nodes from left to right.
  • At even-numbered levels, traverse nodes from right to left.

While traversing a level in the specified direction, process nodes in order and stop immediately before the first node that violates the condition:

  • At odd levels: the node does not have a left child.
  • At even levels: the node does not have a right child.

Only the nodes processed before this stopping condition contribute to the level sum.

Return an integer array ans where ans[i] is the sum of the node values that are processed at level i + 1.

 

Example 1:

Input: root = [5,2,8,1,null,9,6]

Output: [5,8,0]

Explanation:

​​​​​​​

  • At level 1, nodes are processed left to right. Node 5 is included, thus ans[0] = 5.
  • At level 2, nodes are processed right to left. Node 8 is included, but node 2 lacks a right child, so processing stops, thus ans[1] = 8.
  • At level 3, nodes are processed left to right. The first node 1 lacks a left child, so no nodes are included, and ans[2] = 0.
  • Thus, ans = [5, 8, 0].

Example 2:

Input: root = [1,2,3,4,5,null,7]

Output: [1,5,0]

Explanation:

  • At level 1, nodes are processed left to right. Node 1 is included, thus ans[0] = 1.
  • At level 2, nodes are processed right to left. Nodes 3 and 2 are included since both have right children, thus ans[1] = 3 + 2 = 5.
  • At level 3, nodes are processed left to right. The first node 4 lacks a left child, so no nodes are included, and ans[2] = 0.
  • Thus, ans = [1, 5, 0].

 

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • -105 <= Node.val <= 105

Solutions

Solution 1: BFS

Thinking

Recursively gathering each level and then summing a zigzag prefix is heavier than necessary. The required sum stops at the first node that lacks the child implied by the current direction; it is not the sum of the whole level.

BFS already yields nodes level by level. A flag \(\textit{left}\) records the direction: enqueue the next level first, then scan this level from the left or the right, adding a node only while its corresponding child exists.

Flip the flag and replace the queue after each level so a single BFS produces the entire answer.

We use a queue \(q\) to perform a level-order traversal, and define a boolean variable \(\textit{left}\) to indicate the traversal direction of the current level. For each level, we first add the nodes of the next level to the queue \(nq\), and then compute the sum of the node values of the current level, denoted by \(s\), according to the value of \(\textit{left}\), and append \(s\) to the answer array. Finally, we update the value of \(\textit{left}\) and assign \(nq\) to \(q\) to continue traversing the next level.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the number of nodes in the binary tree.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 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 zigzagLevelSum(self, root: TreeNode | None) -> list[int]:
        q = [root]
        ans = []
        left = True
        while q:
            nq = []
            for node in q:
                if node.left:
                    nq.append(node.left)
                if node.right:
                    nq.append(node.right)
            m = len(q)
            s = 0
            for i in range(m):
                node = q[i] if left else q[m - i - 1]
                child = node.left if left else node.right
                if not child:
                    break
                s += node.val
            ans.append(s)
            left = not left
            q = nq
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Long> zigzagLevelSum(TreeNode root) {
        List<Long> ans = new ArrayList<>();
        List<TreeNode> q = new ArrayList<>();
        q.add(root);
        boolean left = true;
        while (!q.isEmpty()) {
            List<TreeNode> nq = new ArrayList<>();
            for (TreeNode node : q) {
                if (node.left != null) {
                    nq.add(node.left);
                }
                if (node.right != null) {
                    nq.add(node.right);
                }
            }
            int m = q.size();
            long s = 0;
            for (int i = 0; i < m; i++) {
                TreeNode node = left ? q.get(i) : q.get(m - i - 1);
                TreeNode child = left ? node.left : node.right;
                if (child == null) {
                    break;
                }
                s += node.val;
            }
            ans.add(s);
            left = !left;
            q = nq;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<long long> zigzagLevelSum(TreeNode* root) {
        vector<long long> ans;
        vector<TreeNode*> q = {root};
        bool left = true;
        while (!q.empty()) {
            vector<TreeNode*> nq;
            for (TreeNode* node : q) {
                if (node->left != nullptr) {
                    nq.push_back(node->left);
                }
                if (node->right != nullptr) {
                    nq.push_back(node->right);
                }
            }
            int m = q.size();
            long long s = 0;
            for (int i = 0; i < m; i++) {
                TreeNode* node = left ? q[i] : q[m - i - 1];
                TreeNode* child = left ? node->left : node->right;
                if (child == nullptr) {
                    break;
                }
                s += node->val;
            }
            ans.push_back(s);
            left = !left;
            q = nq;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelSum(root *TreeNode) []int64 {
    ans := []int64{}
    q := []*TreeNode{root}
    left := true
    for len(q) > 0 {
        nq := []*TreeNode{}
        for _, node := range q {
            if node.Left != nil {
                nq = append(nq, node.Left)
            }
            if node.Right != nil {
                nq = append(nq, node.Right)
            }
        }
        m := len(q)
        var s int64 = 0
        for i := 0; i < m; i++ {
            var node *TreeNode
            if left {
                node = q[i]
            } else {
                node = q[m-i-1]
            }
            var child *TreeNode
            if left {
                child = node.Left
            } else {
                child = node.Right
            }
            if child == nil {
                break
            }
            s += int64(node.Val)
        }
        ans = append(ans, s)
        left = !left
        q = nq
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function zigzagLevelSum(root: TreeNode | null): number[] {
    let q: TreeNode[] = [root];
    const ans: number[] = [];
    let left = true;
    while (q.length > 0) {
        const nq: TreeNode[] = [];
        for (const { left, right } of q) {
            if (left !== null) {
                nq.push(left);
            }
            if (right !== null) {
                nq.push(right);
            }
        }
        const m = q.length;
        let s = 0;
        for (let i = 0; i < m; i++) {
            const node = left ? q[i] : q[m - i - 1];
            const child = left ? node.left : node.right;
            if (child === null) {
                break;
            }
            s += node.val;
        }
        ans.push(s);
        left = !left;
        q = nq;
    }
    return ans;
}

Comments