面试题：使用Java打印 M*N 矩阵从左上角（0，0）到右下角

注：每次只能向右或向下运动一格。
直接看代码：

package com.kaibo.share;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author kaibo
 * @date 2021/7/4 13:27
 * @GitHub：https://github.com/yuxuelian
 * @email：kaibo1hao@gmail.com
 * @description：
 */

public class PrintMatrixPathTest {

    static class MatrixNode {
        private final int xIndex;
        private final int yIndex;
        private final MatrixNode parent;
        private MatrixNode right;
        private MatrixNode bottom;

        public MatrixNode(int xIndex, int yIndex, MatrixNode parent) {
            this.xIndex = xIndex;
            this.yIndex = yIndex;
            this.parent = parent;
        }
    }

    private void printSinglePath(Stack<MatrixNode> tmpPathStack) {
        StringBuilder resPath = new StringBuilder();
        while (!tmpPathStack.isEmpty()) {
            MatrixNode matrixNode = tmpPathStack.pop();
            resPath.append("->(").append(matrixNode.xIndex).append(", ").append(matrixNode.yIndex).append(")");
        }
        System.out.println(resPath.toString());
    }

    private void printPath(MatrixNode rootNode) {
        if (rootNode.right != null) {
            printPath(rootNode.right);
        }
        if (rootNode.bottom != null) {
            printPath(rootNode.bottom);
        }

        if (rootNode.right == null && rootNode.bottom == null) {
            // 是最后一个结点,开始反向遍历父节点
            // 使用栈将路径变为正向流程
            Stack<MatrixNode> tmpPathStack = new Stack<>();
            MatrixNode whileTmp = rootNode;
            while (whileTmp != null) {
                tmpPathStack.push(whileTmp);
                whileTmp = whileTmp.parent;
            }
            // 将栈变成路径输出
            printSinglePath(tmpPathStack);
        }
    }

    /**
     * 创建路径二叉树
     *
     * @param M
     * @param N
     * @return
     */
    private MatrixNode createPathTree(int M, int N) {
        Queue<MatrixNode> matrixNodes = new LinkedList<>();
        MatrixNode rootNode = new MatrixNode(0, 0, null);
        matrixNodes.offer(rootNode);
        while (!matrixNodes.isEmpty()) {
            MatrixNode tmpParent = matrixNodes.poll();
            if (tmpParent.xIndex < M - 1) {
                MatrixNode right = new MatrixNode(tmpParent.xIndex + 1, tmpParent.yIndex, tmpParent);
                // 将自己赋值给父节点的 right 表示父节点能向右运动
                tmpParent.right = right;
                matrixNodes.offer(right);
            }

            if (tmpParent.yIndex < N - 1) {
                MatrixNode bottom = new MatrixNode(tmpParent.xIndex, tmpParent.yIndex + 1, tmpParent);
                // 将自己赋值给父节点的 bottom 表示父节点能向下运动
                tmpParent.bottom = bottom;
                matrixNodes.offer(bottom);
            }
        }
        return rootNode;
    }

    private void printMatrix(int M, int N) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print("(" + i + ", " + j + ") ");
            }
            System.out.println();
        }
    }

    @Test
    public void test() {
        int M = 2;
        int N = 2;

        System.out.println("---------------打印矩阵--------------");
        printMatrix(M, N);
        System.out.println("---------------输出路径--------------");

        // 创建路径树
        MatrixNode rootNode = createPathTree(M, N);
        // 输出路径
        printPath(rootNode);
    }

}

运行结果：
二阶矩阵：

image.png

三阶矩阵：

image.png
3*2阶矩阵：
image.png