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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型二维数组
     */
    public int[][] ZLevelOrder (TreeNode root) {
        // write code here
   if (root == null) {
            return new int[0][0];
        }

        List<int[]> list = new ArrayList<>(); // 存储每层节点值的列表
        Queue<TreeNode> queue = new LinkedList<>(); // 广度优先搜索所用的队列
        queue.offer(root); // 根节点入队
        boolean isLeftToRight = true; // 判断当前层遍历顺序的标志

        // 广度优先搜索进行层序遍历
        while (!queue.isEmpty()) {
            int size = queue.size();
            int[] level = new int[size]; // 当前层节点值的数组
            int index = 0;

            // 遍历当前层的所有节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level[index++] = node.val; // 将节点值存入数组

                // 将左右子节点入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            // 根据遍历顺序确定是否需要反转当前层的节点值数组
            if (!isLeftToRight) {
                reverse(level);
            }

            list.add(level); // 将当前层节点值数组加入列表
            isLeftToRight = !isLeftToRight; // 切换遍历顺序
        }

        // 将列表转换为二维数组作为最终的返回结果
        int[][] result = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }

        return result;
    }

    // 反转数组的方法
    private void reverse(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

知识点：

1. 二叉树的层序遍历：使用广度优先搜索（BFS）来遍历二叉树的每一层节点，并按顺序将节点的值存储在列表中。
2. 数组操作：包括数组的创建、数组元素的赋值、数组的反转等。

代码解释：

• ZLevelOrder 方法接收一个 TreeNode 类型的参数 root，表示二叉树的根节点。返回一个 int[][] 类型的二维数组，表示二叉树的 Z 字形层序遍历结果。
• 在方法中先判断根节点是否为空，如果为空，则直接返回空数组。
• 创建一个列表 list 来存储每层节点值的数组。
• 创建一个队列 queue，并将根节点入队。
• 使用布尔变量 isLeftToRight 来标记当前层是从左到右遍历还是从右到左遍历。
• 进入循环，只要队列不为空，说明还有节点未遍历完。
• 获取当前队列的大小，表示当前层的节点个数。
• 创建一个长度为当前层节点个数的整型数组 level，用于存储当前层的节点值。
• 使用索引 index 表示数组的下标。
• 遍历当前层的所有节点，将节点的值存入数组 level 中。
• 如果节点存在左子节点，则将左子节点入队。
• 如果节点存在右子节点，则将右子节点入队。
• 如果 isLeftToRight 为假（即当前层从右到左遍历），则将数组 level 反转。
• 将数组 level 加入列表 list。
• 切换 isLeftToRight 的值，以切换下一层的遍历顺序。
• 循环结束后，将列表 list 转换为二维数组 result。
• 返回二维数组 result。