一、知识点:
二叉树、遍历、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; } }