每日一题之《剑指offer》17,18,19题

未经本人允许，不得转载
今天心情真好，那么正式开始：

第十七题：树的子结构

难易度：⭐⭐

题目描述:
现在给定 TreeNode类
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

输入两棵树A,B;
判断B是不是A的子结构(我们约定空树不是任意一棵树的子结构)
例如：
A: 
      8
    /   \
   8     7
  / \
 9   2
    / \
   4   7

B:
      8
     / \
    9   2

则：B为A的子结构

本题的思路为：
首先遍历A树，如果遍历到的节点的val值等于B树的根节点的val，那么再去判断以这个节点为根的树是否"包含" B树。本题的重点是对二叉树遍历的考察以及对递归过程的理解。代码中还是有很多细节需要去研究的，比如：当发现A树的某个节点的值等于B树的根节点的值后，如何判断B树包含在A树中？各种case的判定还是比较难想的。
代码如下：

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null){
            return false;
        }
        boolean res = false;
        if(root1.val == root2.val){
            // 判断A树中是否包含B树
            res = doesTree1HaveTree2(root1,root2);
        }
        if(!res){
            res = HasSubtree(root1.left,root2);
        }
        if(!res){
            res = HasSubtree(root1.right,root2);
        }
        return res;
    }
    public boolean doesTree1HaveTree2(TreeNode node1,TreeNode node2){
        if(node2 == null){
            return true;
        }
        if(node1 == null){
            return false;
        }
        if(node1.val != node2.val){
            return false;
        }
        return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
    }
}

第十八题：二叉树的镜像

难易度：⭐

题目描述：
给定TreeNode 类
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
操作给定的二叉树，将其变为源二叉树的镜像
例如：
源二叉树
            8
           /  \
          6   10
         / \  / \
        5  7 9  11
镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7   5

本题思路分析：
二叉树和递归是紧密相连的，因为二叉树的遍历就是递归。不难发现，对二叉树取镜像，实际上就是将每个节点的左子树和右子树交换位置，我们只需要对二叉树先序遍历，然后交换遍历到的节点的左子树和右子树的位置即可。
代码如下：

public class Solution {
    public void Mirror(TreeNode root) {
        if(root != null){
            mirrorProcess(root);
            Mirror(root.left);
            Mirror(root.right);
        }
    }
    public static void mirrorProcess(TreeNode node){
        TreeNode helpNode = node.left;
        node.left = node.right;
        node.right = helpNode;
    }
}

如果对二叉树的遍历不熟悉，需要好好熟悉。面试官有可能继而希望你可以写出非递归的版本：

import java.util.Stack;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root != null){
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                root = stack.pop();
                mirrorProcess(root);
                if(root.right != null){
                    stack.push(root.right);
                }
                if(root.left != null){
                    stack.push(root.left);
                }
            }
        }
    }
    public static void mirrorProcess(TreeNode node){
        TreeNode helpNode = node.left;
        node.left = node.right;
        node.right = helpNode;
    }
}

对于二叉树的先序遍历，中序遍历，后序遍历的非递归实现需要能达到白板coding秒写的程度。

第十九题：顺时针打印矩阵

难易度：⭐⭐

题目描述:
转圈打印矩阵
给定一个整型矩阵matrix，请按照顺时针转圈的方式打印它
例如：
1   2  3  4
5   6  7  8
9  10 11 12
13 14 15 16
打印结果为：
1，2，3，4，8，12，16，15，14，13，9， 5，6，7，11， 10
要求：
额外空间复杂度为O(1)

解题思路：
将顺时针转圈打印转换成一圈一圈地打印，只要知道矩阵左上角的点和矩阵右下角的点就可以将打印出一圈。打印的顺序如图：

import java.util.ArrayList;
public class Solution {
    private ArrayList<Integer> arrayList = new ArrayList<>();
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        int startRow = 0;
        int startColumn = 0;
        int endRow = matrix.length - 1;
        int endColumn = matrix[0].length - 1;
        while(startRow <= endRow && startColumn <= endColumn){
            printProcess(matrix,startRow,startColumn,endRow,endColumn);
            startRow++;
            endRow--;
            startColumn++;
            endColumn--;
        }
        return arrayList;
    }
    public void printProcess(int[][] matrix,int startRow,int startColumn,int endRow,int endColumn){
         if(startRow == endRow && startColumn == endColumn){
             arrayList.add(matrix[startRow][startColumn]);
         }
         if(startRow == endRow && startColumn < endColumn){
            for(int i = startColumn;i <= endColumn;i++){
                arrayList.add(matrix[startRow][i]);
            }
        }
        if(startRow < endRow && startColumn == endColumn){
            for(int i = startRow;i <= endRow;i++){
                arrayList.add(matrix[i][startColumn]);
            }
        }
        if(startRow < endRow && startColumn < endColumn){
            for(int i = startColumn;i < endColumn;i++){
                arrayList.add(matrix[startRow][i]);
            }
            for(int i = startRow;i < endRow;i++){
                arrayList.add(matrix[i][endColumn]);
            }
            for(int i = endColumn;i > startColumn;i--){
                arrayList.add(matrix[endRow][i]);
            }
            for(int i = endRow;i > startRow;i--){
                arrayList.add(matrix[i][startColumn]);
            }
        }
    }
}

代码虽然看上去多，但是捋顺思路后，实际上很简单。