[TOC]

讲清思路

面试时，在编码前应先讲清思路。（可借助画图、举例子，特别是二叉树、二维数组、链表等题目）

通过图像讲解思路，使面试官更轻松理解，是良好沟通能力的体现。

画图

思路：画图

/**
 * https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/
 * 题目：剑指 Offer 27. 二叉树的镜像
 * 难度：简单
 * 思路：交换左右子树
 * */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode left  = mirrorTree(root.left); // 交换左子树的左右子树，并返回左子树
        TreeNode right = mirrorTree(root.right);// 交换右子树的左右子树，并返回右子树
        root.left = right;
        root.right = left;
        return root;
    }
}

对称二叉树

思路：

  • 画图
  • 二叉树的三种遍历方式：前序遍历、中序遍历、后序遍历
/**
 * https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/
 * 题目：剑指 Offer 28. 对称的二叉树
 * 难度：简单
 * 思路：当且仅当满足以下条件时，此二叉树是对称的：
 *  1. 树的左右结点相等
 *  2. （树的左子树的左结点等于右子树的右结点）且（树的左子树的右结点等于右子树的左结点）
 * */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        // 走到这里，说明左右结点同时为 null 不成立，如果此时一个结点是 null，则不是对称二叉树
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

举例

思路：

  • 画图
  • 举例
/**
 * https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
 * 题目：剑指 Offer 29. 顺时针打印矩阵
 * 难度：简单
 * 思路：依次打印
 * 1. 如果顶部大于底部，无需打印；否则打印顶部，消除顶部（行）
 * 2. 如果左边大于右边，无需打印；打印右边，消除右边（列）
 * 3. 如果顶部大于底部，无需打印；打印底部，消除底部（行）
 * 4. 如果左边大于右边，无需打印；打印左边，消除左边（列）
 * */
class Solution {
    private int[][] matrix;
    private int[] result;
    private int index;
    private int top;
    private int bottom;
    private int left;
    private int right;

    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        this.matrix = matrix;
        int rows = matrix.length;
        int cols = matrix[0].length;

        result = new int[rows * cols];
        index = 0;

        top = 0;
        left = 0;
        bottom = matrix.length - 1;
        right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            printTop();
            printRight();
            printBottom();
            printLeft();
        }
        return result;
    }

    private void printTop() {
        if (top > bottom) {
            return;
        }
        for (int i = left; i <= right; i++) {
            result[index++] = matrix[top][i];
        }
        top++;
    }

    private void printRight() {
        if (left > right) {
            return;
        }
        for (int i = top; i <= bottom; i++) {
            result[index++] = matrix[i][right];
        }
        right--;
    }

    private void printBottom() {
        if (top > bottom) {
            return;
        }
        for (int i = right; i >= left; i--) {
            result[index++] = matrix[bottom][i];
        }
        bottom--;
    }

    private void printLeft() {
        if (left > right) {
            return;
        }
        for (int i = bottom; i >= top; i--) {
            result[index++] = matrix[i][left];
        }
        left++;
    }
}

todo: 第四章剩余内容

参考

  • 《剑指Offer》（第二版）