面试题【27-29】画图让抽象问题形象化

面试题27：二叉树的镜像

题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。

public TreeNode mirrorTree(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) {
        return root;
    }

    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    if (root.left != null) {
        root.left = mirrorTree(root.left);
    }
    if (root.right != null) {
        root.right = mirrorTree(root.right);
    }
    return root;
}

面试题28：对称的二叉树

题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

public boolean isSymmetric(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) {
        return true;
    }
    return isSymmetricLeftRight(root.left, root.right);
}
private boolean isSymmetricLeftRight(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null) {
        return false;
    }
    if (left.val != right.val) {
        return false;
    }
    return isSymmetricLeftRight(left.left, right.right) && isSymmetricLeftRight(left.right, right.left);
}

面试题29：顺时针打印矩阵

题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0) {
            return list;
        }

        spiralOrder(matrix, list, 0);
        return list;
    }

    public void spiralOrder(int[][] matrix, ArrayList<Integer> list, int start) {
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i = start; i < col - start; i++) {
            list.add(matrix[start][i]);
        }
        for (int i = start + 1; i < row - start; i++) {
            list.add(matrix[i][col-1-start]);
        }
        if (list.size() ==  row * col) {
            return;
        }
        for (int i = col - 2 - start; i >= start; i--) {
            list.add(matrix[row-1-start][i]);
        }
        for (int i = row - 2 - start; i > start; i--) {
            list.add(matrix[i][start]);
        }
        if (list.size() ==  row * col) {
            return;
        }
        spiralOrder(matrix, list, start+1);
    }

public int[] spiralOrder(int[][] matrix) {
    if (matrix == null || matrix.length == 0) {
        return new int[0];
    }
    for (int i = 0; i < matrix.length; i++) {
        if (matrix[i] == null || matrix[i].length == 0) {
            return new int[0];
        }
        if (i > 1 && matrix[i].length != matrix[i-1].length) {
            return new int[0];
        }
    }

    int start = 0, rows = matrix.length, cols = matrix[0].length;
    int[] result = new int[rows * cols];
    int count = 0;
    while (rows > start << 1 && cols > start << 1) {
        count = spiralOrderBegin(matrix, start, result, count);
        start++;
    }
    return result;
}
public int spiralOrderBegin(int[][] matrix, int start, int[] result, int count) {
    int endRows = matrix.length - 1 - start;
    int endCols = matrix[0].length - 1 - start;

    for (int i = start; i <= endCols; i++) {
        result[count++] = matrix[start][i];
    }
    if (endRows > start) {
        for (int i = start + 1; i <= endRows; i++) {
            result[count++] = matrix[i][endCols];
        }
    }
    if (endRows > start && endCols > start) {
        for (int i = endCols - 1; i >= start; i--) {
            result[count++] = matrix[endRows][i];
        }
    }
    if (endCols > start && endRows - 1 > start) {
        for (int i = endRows - 1; i > start; i--) {
            result[count++] = matrix[i][start];
        }
    }
    return count;
}