使用递归解决螺旋矩阵问题

面试时被要求写一段代码，螺旋输出一个二维数组。比如，对于下面这个二维数组，要求按图示的方向进行元素的输出：

由于平时专注写业务，很少关注算法，这个问题一下把我整蒙了(shy…)，思维打不开，到最后也没回答上来。

昨晚睡觉前又思考了一翻这个问题，想到削苹果的场景，如果在削苹果时，按同一个方向一层一层的往里削，等把苹果连皮带核削完时(残忍吧)，整个(苹果)矩阵也就遍历结束了。

于是我想，在螺旋遍历过程中，把遍历的元素都给移除掉(相当于削皮)，第一层移除完后，再递归移除剩下的，直到没有可移除的，问题不就解决了吗？

接着想，怎么削第一层皮？

观察上图，对于二维数组来说，第一层皮显然是由数组的第一行、最后一列、最后一行、第一列组成的（注意这个顺时针的顺序）。我们用变量 step 代表这个顺序，其是 number 类型，取值 0 到 3，当 step 等于：

0: 表示要从左到右输出矩阵的第一行；
1: 表示要从上到下输出矩阵的最后一列；
2: 表示要从右到左输出矩阵的最后一行；
3: 表示要从下往上输出矩阵的第一列；

再次强调，输出的过程也是从矩阵中移除这些元素的过程。当 step = 3 的逻辑执行完后，我们再递归从 0 开始。

所以整个螺旋输出矩阵元素的代码如下：

function spiralOrder(matrix) {
    // 方法返回值
    const res = [];
    // 往返回值中追加数据
    const append = (v) => res.push(v);

    // 递归遍历
    traverse(matrix);

    // 返回螺旋收集的值
    return res;

    /**
     * 递归螺旋遍历矩阵
     *
     * @param arr 待遍历的矩阵数据
     * @param step 走到第几步了
     */
    function traverse(arr, step = 0) {
        if (!arr?.length) {
            return;
        }

        // 遍历首行
        if (step === 0) {
            const [first] = arr;
            if (!first?.length) {
                // 遍历完了
                return;
            }
            first.forEach(append);
            traverse(arr.slice(1), step + 1);
            return;
        }

        // 遍历最后一列
        if (step === 1) {
            arr.forEach((v) => append(v.pop()));
            traverse(arr, step + 1);
            return;
        }

        // 遍历最后一行
        if (step === 2) {
            const last = arr.pop();
            if (!last?.length) {
                // 遍历完了
                return;
            }
            last.reverse().forEach(append);
            traverse(arr, step + 1);
            return;
        }

        // 遍历第一列
        if (step === 3) {
            arr.forEach((v, i, a) => {
                const row = a.length - i - 1;
                append(a[row].shift());
            });
            // 回到开始
            traverse(arr);
        }
    }
}

测试看看：

const h = [
    [1, 2, 3],
    [8, 9, 4],
    [7, 6, 5],
];

const i = [
    [1,  2,  3],
    [10, 11, 4],
    [9,  12, 5],
    [8,  7,  6],
];

[h, i].forEach((v) => {
    console.log('#'.repeat(10));
    console.log(v);
    const res = spiralOrder(v);
    console.log(res);
});