题解 | #牛群Z字型排列#

牛群Z字型排列

https://www.nowcoder.com/practice/50ddaf50c6954600a9f1dbb099d6f388

一、知识点:

二叉树、遍历、BFS

二、文字分析:

使用了广度优先搜索(BFS)算法来遍历二叉树的每一层,并将每层的牛的编号存储在一个二维列表中。我们使用一个队列来保存当前层的节点,并根据 reverse 变量决定是否翻转当前层的顺序。当 reverse 为 true 时,说明当前层应该从右往左遍历,我们使用 Collections.reverse() 方法将当前层列表翻转。最后,我们将每个层的列表添加到结果列表中,并将结果转换为二维数组。

时间复杂度为 O(N),空间复杂度为 O(N)。这里的 N 表示二叉树中的节点数。

三、编程语言:

java

四、正确代码:

import java.util.*;

public class Solution {
    public int[][] ZLevelOrder(TreeNode root) {
        if (root == null) {
            return new int[0][];
        }

        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean reverse = false;

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            if (reverse) {
                Collections.reverse(level);
            }

            result.add(level);
            reverse = !reverse;
        }

        int[][] resArray = new int[result.size()][];
        for (int i = 0; i < result.size(); i++) {
            List<Integer> level = result.get(i);
            int[] levelArray = new int[level.size()];
            for (int j = 0; j < level.size(); j++) {
                levelArray[j] = level.get(j);
            }
            resArray[i] = levelArray;
        }

        return resArray;
    }
}

全部评论

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务