3902. Zigzag Level Sum of Binary Tree 🔒

题目描述

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, 10⁵].
-10⁵ <= Node.val <= 10⁵

解法

方法一：BFS

我们使用一个队列 \(q\) 来进行层序遍历，定义一个布尔变量 \(\textit{left}\) 来表示当前层的遍历方向。对于每一层，我们先将下一层的节点加入队列 \(nq\) 中，然后根据 \(\textit{left}\) 的值来计算当前层的节点值之和 \(s\)，并将 \(s\) 添加到答案数组中。最后，更新 \(\textit{left}\) 的值，并将 \(nq\) 赋值给 \(q\) 以继续下一层的遍历。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是二叉树中节点的数量。

Python3JavaC++GoTypeScript

# 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.
 * 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.
 * 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;
}

3902. Zigzag Level Sum of Binary Tree 🔒

题目描述

解法

方法一：BFS

评论