Welcome to Subscribe On Youtube

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

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.

  • /**
 * 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;
    }
}


  • /**
 * 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;
    }
};


  • # 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


  • /**
 * 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
}


  • /**
 * 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;
}

All Problems

All Solutions