跳转至

3902. 二叉树的 Z 字形层级和 🔒

题目描述

给定一棵 二叉树 的根节点 root。

按 Z 字形模式逐层遍历树：

  • 在 奇数 层（下标从 1 开始）中，从左到右 遍历节点。
  • 在 偶数 层，从右到左 遍历节点。

在指定方向遍历某一层时，按顺序处理节点，并立即在第一个违反条件的节点前 停止：

  • 在 奇数 层：该节点没有 左 子节点。
  • 在 偶数 层：该节点没有 右 子节点。

只有在此停止条件之前的节点对层级和有贡献。

返回一个整数数组 ans，其中 ans[i] 是在第 i + 1 层处理的节点值之 和。

 

示例 1：

输入：root = [5,2,8,1,null,9,6]

输出：[5,8,0]

解释：

​​​​​​​

  • 在第 1 层，从左往右处理节点。节点 5 被包含，因此 ans[0] = 5。
  • 在第 2 层，从右往左处理节点。节点 8 被包含，但节点 2 缺少一个右儿子，所以处理中断，因此 ans[1] = 8。
  • 在第 3 层，从左往右处理节点。第一个节点 1 缺少一个左儿子，因此没有节点被包含，因此 ans[2] = 0。
  • 因此，ans = [5, 8, 0]。

示例 2：

输入：root = [1,2,3,4,5,null,7]

输出：[1,5,0]

解释：

  • 在第 1 层，从左往右处理节点。节点 1 被包含，因此 ans[0] = 1。
  • 在第 2 层，从右往左处理节点。节点 3 和 2 被包含，因为它们都有右儿子，因此 ans[1] = 3 + 2 = 5。
  • 在第 3 层，从左到右进行处理节点。第一个节点 4 没有左子节点，因此不包含任何节点，因此 ans[2] = 0。
  • 因此，ans = [1, 5, 0].

 

提示：

  • 树中的节点数范围为 [1, 105]。
  • -105 <= Node.val <= 105

解法

方法一：BFS

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

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

 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;
}

评论