剑指offer--Java版

解题视频https://www.bilibili.com/video/BV1cz4y1S7AX?p=1

剑指offer 03.数组中的重复数字

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int repeat = -1;
        for(int num:nums){
            if(!set.add(num)){
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}

剑指offer 04.二维数组中的查找

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int row = 0;
        int col = cols - 1;
        while(row < rows && col >=0){
            if(matrix[row][col] == target){
                return true;
            }else if(matrix[row][col] > target){
                col--;
            }else{
                row++;
            }
        }
        return false;
    }
}

剑指offer 05.替换空格

class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] carry  = new char[length * 3];
        int size = 0;
        for(int i = 0; i< length; i++){
            char c = s.charAt(i);
            if(c == ' '){
                carry[size++] = '%';
                carry[size++] = '2';
                carry[size++] = '0';
            }else{
                carry[size++] = c;
            }
        }
        String newStr = new String(carry,0,size);
        return newStr;
    }
}

剑指offer 06.从尾到头打印链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null){
            return new int[]{};
        }
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while(cur != null){
            stack.push(cur.val);
            cur = cur.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = stack.pop();
        }
        return res;
    }
}

剑指offer 07.重建二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0){
            return null;
        }
        HashMap<Integer,Integer> hashmap = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            hashmap.put(inorder[i],i);
        }
        return dfs(preorder,0,preorder.length - 1,0,hashmap);
    }
    public TreeNode dfs(int[] preorder,int pl,int pr,int il,HashMap<Integer,Integer> hashmap){
        if(pl > pr){
            return null;
        }
        TreeNode curRoot = new TreeNode(preorder[pl]);
        int k = hashmap.get(curRoot.val);
        curRoot.left = dfs(preorder,pl+1,pl+(k-il),il,hashmap);
        curRoot.right = dfs(preorder,pl+(k-il)+1,pr,k+1,hashmap);
        return curRoot;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0){
            return null;
        }
        Map<Integer, Integer> indexMap = new HashMap<>();
        int length = preorder.length;
        for(int i = 0; i < length; i++){
            indexMap.put(inorder[i],i);
        }
        TreeNode root = buildTree(preorder,0,length -1,inorder,0,length-1,indexMap);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int preorderStart,int preorderEnd,int[] inorder,int inorderStart,int inorderEnd,Map<Integer,Integer> indexMap){
        if(preorderStart > preorderEnd){
            return null;
        }
        int rootVal = preorder[preorderStart];
        TreeNode root = new TreeNode(rootVal);
        if(preorderStart == preorderEnd){
            return root;
        }else{
            int rootIndex = indexMap.get(rootVal);
            int leftNodes = rootIndex - inorderStart,rightNodes = inorderEnd - rootIndex;
            TreeNode leftSubtree = buildTree(preorder,preorderStart+1,preorderStart+leftNodes,inorder,inorderStart,rootIndex -1,indexMap);
            TreeNode rightSubtree = buildTree(preorder,preorderEnd - rightNodes + 1,preorderEnd,inorder,rootIndex + 1,inorderEnd,indexMap);
            root.left = leftSubtree;
            root.right = rightSubtree;
            return root;
        }
    }
}

剑指offer 09.用两个栈实现队列

class CQueue {
    private Stack<Integer> stackin;
    private Stack<Integer> stackout;
    public CQueue() {
        stackin = new Stack<>();
        stackout = new Stack<>();
    }
    public void appendTail(int value) {
        stackin.push(value);
    }
    public int deleteHead() {
        if(stackout.isEmpty()){
            while(!stackin.isEmpty()){
                stackout.push(stackin.pop());
            }
        }
        if(!stackout.isEmpty()){
            return stackout.pop();
        }else{
            return -1;
        }
    }
}
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

class CQueue {
    private Deque<Integer> stackin;
    private Deque<Integer> stackout;
    public CQueue() {
        stackin = new LinkedList<>();
        stackout = new LinkedList<>();
    }
    public void appendTail(int value) {
        stackin.push(value);
    }
    public int deleteHead() {
        if(stackout.isEmpty()){
            while(!stackin.isEmpty()){
                stackout.push(stackin.pop());
            }
        }
        if(!stackout.isEmpty()){
            return stackout.pop();
        }else{
            return -1;
        }
    }
}
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

剑指offer 10-1.斐波那契数列

class Solution {
    public int fib(int n) {
        if(n == 0){
            return 0;
        }
        int a = 0;
        int b = 1;
        int sum = 0;
        for(int i= 0; i < n; i++){
            sum = (a+b)%1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

剑指offer 10-2.青蛙跳台阶问题

剑指offer 11.旋转数组的最小数字

class Solution {
    public int minArray(int[] numbers) {
        int low = 0;
        int hight = numbers.length - 1;
        while(low < hight){
            int pivot = low + (hight - low)/2;
            if(numbers[pivot] < numbers[hight]){
                hight = pivot;
            }else if(numbers[pivot] > numbers[hight]){
                low = pivot + 1;
            }else if(numbers[pivot] == numbers[hight]){
                hight--;
            }
        }
        return numbers[low];
    }
}

剑指offer 12.矩阵中的路径

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0) return false;
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] isVisited = new boolean[rows][cols];//标记数组
        //路径可以从矩阵中任意一格开始，所以分别以矩阵中的每一个字符作为起点寻找
        for(int i = 0; i < rows;i++){
            for(int j = 0; j < cols; j++){
                if(dfs(board,word,0,i,j,isVisited)){
                    return true;
                }
            }
        }
         return false;
    }
    //参数说明，n表示当前访问到第几个字符了，（x,y）表示当前要访问的字符在board中的坐标
    private boolean dfs(char[][] board,String word,int n,int x,int y,boolean[][] isVisited){
        //当前位置和我们需要的字符word.charAt(n)不同，该路径行不通
        if(board[x][y] != word.charAt(n)) return false;
        //我们要查找的最后一个字符都通过了上面那条if语句，该单词路径存在
        if(n == word.length() - 1) return true;
        isVisited[x][y] = true;//标记board[x][y]已经被访问过了
        //定义左右上下四个方向(偏移量技巧）
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};
        for(int i = 0; i < 4;i++){//分别尝试往左右上下四个方向走
            //改变方向，注意这里不是用x = x+dx[i],而是用a和b接收，以保证下轮循环时x,y是原来的值
            int a = x + dx[i];
            int b = y + dy[i];
            //保证a,b不越界，且board[a][b]还未被访问过
            if(a >= 0 && a < board.length && b >= 0 && b < board[0].length && !isVisited[a][b]){
                 if(dfs(board,word,n+1,a,b,isVisited)){
                     return true;
                }
            }
        }
        isVisited[x][y] = false; //状态回退
        return false;
    }
}

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(dfs(board, words, i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, char[] word, int i, int j, int k){
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]){
            return false;
        }
        if(k == word.length - 1){
            return true;
        }
        board[i][j] = '\0';
        boolean res = dfs(board, word, i+1, j, k+1) || dfs(board, word, i - 1, j, k+1) ||
                dfs(board, word, i, j + 1, k+1) || dfs(board, word, i ,j -1, k+1);
        board[i][j] = word[k];
        return res;
    }
}

剑指offer 13.机器人的运动范围

递归参数的设置，与变量的作用域有关，局部 变量不可以调用，必须设置为全局变量才可以

class Solution {
    private int count = 0;
    public int movingCount(int m, int n, int k) {
        if(m < 0||n < 0){
            return -1;
        }
        boolean[][] isVisited = new boolean[m][n];
        dfs(m,n,k,isVisited,0,0);
        return count;
    }
    private void dfs(int m,int n,int k,boolean[][] isVisited,int x,int y){
        //坐标越界或者已经访问过，直接返回退出本次调用栈
        if(x < 0 || x >=m||y < 0 ||y >= n|| isVisited[x][y]){
            return;
        }
        isVisited[x][y] = true;//标记该坐标访问过了；
        //当确定机器人可以进入该坐标之后，才需要从这坐标向四个方向扩散
        if(getSum(x,y) <= k){
            count++;
            int[] dx = {-1,1,0,0};
            int[] dy = {0,0,-1,1};
            for(int i = 0; i < 4; i++){
                int a = x + dx[i];
                int b = y + dy[i];
                dfs(m,n,k,isVisited,a,b);
            }
        }else{
            return;          //机器人无法到达
        }
    }
    private int getSum(int x,int y){
        int res = 0;
        while(x > 0){
            res += x % 10;
            x /=10;
        }
        while(y > 0){
            res += y % 10;
            y /= 10;
        }
        return res;
    }
}

剑指offer 14-|.减绳子

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3){
            return n-1;
        }
        int a = n/3;
        int b = n%3;
        if(b == 1){
            return (int)Math.pow(3,(a-1))*4;
        }
        if(b == 0){
            return (int)Math.pow(3,a);
        }
        return (int)Math.pow(3,a)*2;
    }
}

剑指offer 14-||.减绳子||

class Solution {
    public int cuttingRope(int n) {
        if(n<=3) return n-1;
        int a=n/3;
        int b=n%3;
        //循环a-1次：res=pow(3,a-1)
        long res=1;
        int mod=1000000007;
        for(int i=0;i<a-1;i++){
            res=res*3;
            res=res%mod;
        }
        if(b==0)//乘3 pow(3,a)
            return (int)(res*3%mod);
        if(b==1)//乘4 pow(3,a-1)*4
            return (int)(res*4%mod);
        else//乘3 乘2 pow(3,a)*2
            return (int)((res*3%mod)*2%mod);
    }
}

剑指offer 15.二进制中1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
        while(n != 0){
            result = result + (n & 1);
            n = n >>> 1;
        }
        return result;
    }
}

剑指offer 16.数值的整数次方

class Solution {
    public double myPow(double x, int n) {
        //快速幂
        //n可以用二进制表示
        //9=1001=1*1 + 0*2 + 0*4 + 1*8
        //x^9 = x^(1*1) x^(0*2) x^(0*4) x^(1*8)
        if(x == 0){
            return 0;
        }
        //int范围[−2147483648,2147483647]，当n = -2147483648，时执行 n = -n会越界，使用long类型
        long b = n;
        double  res = 1.0;
        if(b < 0){
            b = -b;
            x = 1/x;
        }
        while(b > 0){
            if((b & 1) == 1){
                res = res * x;   //累乘   //指数
            }
            x = x * x;           //相当于x^2       //底数   每次都要平方
            b = b >>> 1;         //右移一位
        }
        return res;
    }
}

剑指offer 17.打印从1到最大的n位数

class Solution {
    public int[] printNumbers(int n) {
        if(n <= 0){
            return new int[0];
        }
        int max = (int)Math.pow(10, n);
        int[] arr = new int[max - 1];
        for(int i = 0; i < max-1; i++){
            arr[i] = i + 1;
        }
        return arr;
    }
}

剑指offer 18.删除链表的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode domp = new ListNode(-1);
        domp.next = head;
        ListNode tem = domp;
        while(tem.next != null){
            if(tem.next.val == val){
                tem.next = tem.next.next;
                break;
            }
            tem = tem.next;
        }
        return domp.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head == null){
            return head;
        }
        if(head.val == val){
            return head.next;
        }
        ListNode pre = head;
        ListNode last = head.next;
        while(last.next != null && last.val != val){
            pre = last;
            last = last.next;
        }
        pre.next = (last == null) ? null:last.next;
        return head;
    }
}

剑指offer 19.正则表达式匹配

class Solution {
    static boolean[][] dp;
    static int n,m;
    public static boolean isMatch(String s, String p){
        char[] ss = s.toCharArray();
        char[] ps = p.toCharArray();
        dp = new boolean[ss.length + 1][ps.length + 1];
        n = ss.length;
        m = ps.length;
        dp[n][m] = true;
        return dp(0,0,ss,ps);
    }
    private static boolean dp(int i, int j, char[] ss, char[] ps){
        if (dp[i][j]){
            return dp[i][j];
        }
        // 模式串匹配完成，判断是否匹配完字符串
        if (j == m){
            return dp[i][j] = i == n;
        }
        // 出现两个串字符相同或者模式串为'.'时则为true
        boolean firstMatch = i < n && (ss[i] == ps[j] || ps[j] == '.');
        boolean ans;
        if (j + 1 < m && ps[j + 1] == '*'){
            // j + 2意味着 *号和之前的一个元素没有被匹配到则跳过
            ans = dp(i,j + 2, ss, ps) || firstMatch && dp(i + 1, j, ss, ps);
        }else {
            ans = firstMatch && dp(i + 1, j + 1, ss, ps);
        }
        return dp[i][j] = ans;
    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for(int i = 0; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                if(p.charAt(j - 1) == '*'){
                    f[i][j] = f[i][j - 2];
                    if(matches(s, p ,i , j - 1)){
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                }else{
                    if(matches(s, p, i, j)){
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
    public boolean matches(String s, String p, int i, int j){
        if(i == 0){
            return false;
        }
        if(p.charAt(j - 1) == '.'){
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

剑指offer 20.表示数值的字符串

class Solution {
    public boolean isNumber(String s) {
        int n = s.length();
        int index = 0;
        boolean hasNum = false, hasE = false;
        boolean hasSign = false, hasDot = false;
        while(index < n && s.charAt(index) == ' ')
            index++;
        while(index < n){
            while(index < n && s.charAt(index) >= '0' && s.charAt(index) <= '9'){
                index++;
                hasNum = true;
            }
            if(index == n){
                break;
            }
            char c = s.charAt(index);
            if(c == 'e' || c == 'E'){
                if(hasE || !hasNum){
                    return false;
                }
                hasE = true;
                hasNum = false; hasSign = false; hasDot = false;
            }else if(c == '+' || c == '-'){
                if(hasSign || hasNum || hasDot){
                    return false;
                }
                hasSign = true;
            }else if(c == '.'){
                if(hasDot || hasE){
                    return false;
                }
                hasDot = true;
            }else if(c == ' '){
                break;
            }else{
                return false;
            }
            index++;
        }
        while(index < n && s.charAt(index) == ' ')
            index++;
        return hasNum && index == n;
    }
}

剑指offer 21.调整数组顺序使奇数位于偶数前

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0) return nums;
        int[] res = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] % 2 != 0){
                res[left++] = nums[i];        //奇数从前往后放
            }else{
                res[right--] = nums[i];       //偶数从后往前放
            }
        }
        return res;
    }
}

class Solution {
    public int[] exchange(int[] nums) {
        if(nums.length == 0){
            return nums;
        }
        int length = nums.length;
        int length1 = length - 1;
        int length2 = 0;
        int[] arr = new int[length];
        for(int i = 0; i < length; i++){
            if(nums[i] % 2 != 0){
                arr[length2] = nums[i];
                length2++;
            }else{
                arr[length1] = nums[i];
                length1--;
            }
        }
        return arr;
    }
}

剑指offer 22.链表中倒数第k个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fir = head;
        ListNode sec = head;
        for(int i = 0; i < k; i++){
            fir = fir.next;
        }
        while(fir != null){
            fir = fir.next;
            sec = sec.next;
        }
        return sec;
    }
}

剑指offer 24.反转链表

/*** Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

剑指offer 25.合并两个排序的链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode p1 = l1;                  //用于遍历l1
        ListNode p2 = l2;                  //用于遍历l2
        ListNode dummy = new ListNode(0);  //新建链表虚拟头节点
        ListNode cur = dummy;              //辅助构建新链表
        //两个链表都未遍历结束时，比较当前节点的大小，拼接到新链表之后
        while(p1 != null && p2 != null){
            if(p1.val < p2.val){
                cur.next = p1;
                p1 = p1.next;
                cur = cur.next;
            }else{
                cur.next = p2;
                p2 = p2.next;
                cur = cur.next;
            }
        }
        //退出while循环后，说明肯定有一个链表遍历结束
        if(p1 == null){
            cur.next = p2;
        }
        if(p2 == null){
            cur.next = p1;
        }
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode pom = new ListNode(0);
        ListNode cur = pom;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1:l2;
        return pom.next;
    }
}

剑指offer 26.树的子结构

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        //直接判断A是否是B作为根节点的开始的一部分，不是再递归A，让A的左右节点分别作为新树的根节点
        if(isPart(A,B)) return true;
        return isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
    public boolean isPart(TreeNode A,TreeNode B){
        //A和B根节点相同，再递归的判断他们各自的左右节点的值是否相同，递归的终止条件是：
        //到达了树A或树B的叶子节点，或者两个的值不相等
        if(B == null) return true;
        //通过上面的if判断，说明B当前节点不是空，
        //如果此时A空了，或者A和B当前节点的值不同，则B不是A的子结构
        if(A == null || A.val != B.val) return false;
        return isPart(A.left, B.left) && isPart(A.right, B.right);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (res(A,B) || isSubStructure(A.left, B) || isSubStructure(A.right,B));
    }
    private boolean res(TreeNode A, TreeNode B){
        if(B == null){
            return true;
        }
        if(A == null || A.val != B.val){
            return false;
        }
        return res(A.left, B.left) && res(A.right, B.right);
    }
}

剑指offer 27.二叉树的镜像

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        //前序遍历二叉树，将非叶子节点的左右节点互换一下即可
        if(root == null) return null;
        swap(root);
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
    //交换根节点的左右子节点，root的左右孩子是null也可以用swap函数，只要root不是null即可
    //毕竟root是null,root.legt root.right就空指针异常了
    private void swap(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

剑指offer 28.对称的二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//递归判断两个子树是否互为镜像。
//两个子树互为镜像当且仅当：
//1. 两个子树的根节点值相等；
//2. 第一棵子树的左子树和第二棵子树的右子树互为镜像，且第一棵子树 的右子树和第二棵子树的左子树互为镜像。
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return dfs(root,root);
    }
    public boolean dfs(TreeNode p, TreeNode q){
        if(p == null && q == null) return true; //两树空视为想等
        if(p == null || q == null) return false; //结合上一个if，代表一个为空，另一个不为空，不可能相等
        if(p.val != q.val) return false; //镜像的值不同
        return dfs(p.left, q.right) && dfs(p.right, q.left);
    }
}

剑指offer 29.顺序打印矩阵

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int l = 0;                       //左边界
        int r = matrix[0].length-1;      //右边界
        int t = 0;                       //上边界
        int b = matrix.length - 1;       //下边界
        int x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true){
            for(int i = l;i <= r;i++) res[x++] = matrix[t][i];// left to right.
            if(++t > b) break;
            for(int i = t;i <= b;i++) res[x++] = matrix[i][r];// top to bottom.
            if(l > --r) break;
            for(int i = r;i >= l;i--) res[x++] = matrix[b][i];// right to left.
            if(t > --b) break;
            for(int i = b;i >= t;i--) res[x++] = matrix[i][l];// bottom to top.
            if(++l > r) break;
        }
        return res;
    }
}