leetcode498. 对角线遍历

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]
示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

思路：使用递归大法

class Solution {

    int index = 0;
    public int[] findDiagonalOrder(int[][] mat) {
        index = 0;
        int[] arr = new int[mat.length * mat[0].length];
        dfs(mat,0, 0, 1, arr);
        return arr;
    }

    public void dfs(int[][] mat, int row, int col, int direction, int[] arr) {
        //System.out.println(mat[row][col]);
        arr[index++] = mat[row][col];
        if (direction == 1) {//往上
            int nextrow = row - 1;
            int nextcol = col + 1;
            if (nextrow >= 0 && nextcol < mat[0].length) {//可以往上
                dfs(mat, nextrow, nextcol, direction, arr);
            } else {//不能往上

                if (nextcol < mat[0].length) {//可以往左
                    dfs(mat, row, nextcol, 0, arr);
                } else if (row + 1 < mat.length){//可以往下
                    dfs(mat, row + 1, col, 0, arr);
                }

            }
        } else {//往下
            int nextrow = row + 1;
            int nextcol = col - 1;
            if (nextrow < mat.length && nextcol >= 0) {//可以往下
                dfs(mat, nextrow, nextcol, direction, arr);
            } else {//不能往下
                if (nextrow < mat.length) {//可以垂直向下
                    dfs(mat, nextrow, col, 1, arr);
                } else if (col + 1 < mat[0].length) {//可以往左
                    dfs(mat, row, col + 1, 1, arr);
                }
            }
        }
    }
}