题解 | #对角线遍历矩阵#

import java.util.*;


public class Solution {
    
    // 自定义一个类，表示的是每个点的坐标以及该点上的值
    public class Coordinates {
        public int x; // x 坐标
        public int y; // y 坐标
        public int val; // 值
        public int level; // 层次
        public Coordinates(int x, int y, int val, int level) {
            this.x = x;
            this.y = y;
            this.val = val;
            this.level = level;
        }
    }
    
    public ArrayList<Integer> res = new ArrayList<>(); // 定义一个一维数组，用于存放最终的遍历结果
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型二维数组 
     * @return int整型一维数组
     */
    public int[] diagonalOrder (int[][] mat) {
        // write code here
        
        int n = mat.length; // 获取 n
        int m = mat[0].length; // 获取 m
        // 定义一个二维数组，用于存放当前位置是否已经被访问过
        int[][] sign = new int[n][m]; // 0: 表示未访问过    1: 表示访问过
        
        // 广度优先遍历(BFS)
        Queue<Coordinates> queue = new LinkedList<>(); // 定义一个队列
        Coordinates coordinates = new Coordinates(0, 0, mat[0][0], 1); // 初始化位置
        Coordinates tmp = coordinates; // 定义一个辅助 Coordinates
        Stack<Integer> stack = new Stack<>(); // 定义一个栈，用于逆序输出偶数层的值
        
        queue.add(coordinates); // 将初始位置添加到队列里面去
//         int currentLevel = 1; // 定义一个整型变量，用于存放当前所在的层次
        
        while (!queue.isEmpty()) {
            tmp = queue.poll(); // 从队列当中出队一个位置
            if (sign[tmp.x][tmp.y] == 0) { // 如果当前位置未被访问过
                if (tmp.level % 2 == 0) { // 如果当前位置所在的层次是偶数层
                    while (!stack.isEmpty()) {
                        res.add(stack.pop());
                    }
                    res.add(tmp.val); // 将当前位置的值添加到 res 遍历结果当中
                    sign[tmp.x][tmp.y] = 1; // 同时记录该位置已经被访问过
                }
                else { // 如果当前位置所在的层次是奇数层
                    stack.push(tmp.val);
                    sign[tmp.x][tmp.y] = 1;
                }
            }
            
            if (tmp.y + 1 < m) { // 如果当前位置的右边一位存在(不越界)
                Coordinates rightCoordinates = new Coordinates(tmp.x, tmp.y + 1, mat[tmp.x][tmp.y + 1], tmp.level + 1); // 创建一个 Coordinates
                queue.add(rightCoordinates); // 将 Coordinates 添加到队列中去
            }
            if (tmp.x + 1 < n) {
                Coordinates downCoordinates = new Coordinates(tmp.x + 1, tmp.y, mat[tmp.x + 1][tmp.y], tmp.level + 1);
                queue.add(downCoordinates);
            }
        }
        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}