【剑指】4.2 画图形象化抽象问题

在一些涉及树、图、矩阵的题目中，可以尝试使用画图来帮助自己理清思路。

面试题27：二叉树的镜像

题目描述

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

解题思路

我们可以根据描述画出这样的例图：

       8 
      /\
   6      10 
  /\      /\
5   7   9   11

       8 
      /\
   10      6
  /\      /\
11   9   7   5

不难看出，镜像就是对于每一个节点交换其左右孩子节点，并递归地对孩子节点执行该操作。那么我们可以写出如下代码：

public TreeNode getMirror(TreeNode root){
    if(root==null) return null;
    TreeNode temp=root.left;
    root.left=root.right;
    root.right=temp;
    root.left=getMirror(root.left);
    root.right=getMirror(root.right);
    return root;
}

面试题28：对称的二叉树

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解题思路

我们可以画出一张例图：

       8 
      /\
   6      6 
  /\      /\
5   7   7   5

那么可以发现，问题可以转为对于输入的两个节点A和B，如果A的左孩子等于B的右孩子且A的右孩子等于B的左孩子，那么A和B是镜像的树。如果A和B是同一个节点，那么该树就是对称的树。

public boolean isSymmetrical(TreeNode root){
    return isSymmetrical(root,root);
}

private boolean isSymmetrical(TreeNode rootA, TreeNode rootB){
    if(rootA==null && rootB==null) return true;
    if(rootA==null || rootB==null) return false;
    if(rootA.val==rootB.val) return isSymmetrical(rootA.left,rootB.right)&&isSymmetrical(rootA.right,rootB.left);
    return false;
}

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

题目描述

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

示例：

输入矩阵： 
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.

解题思路

例图就在上面的示例中了，我们可以人为地在图中画上（限定出）上下左右四条边界，每次完成一个方向地输出后改变对应地边界并检查是否有边界重合，如果发现重合则循环结束。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> result=new ArrayList<>();
        if(matrix==null||matrix[0]==null) return result;
        int left=0,right=matrix[0].length-1,up=0,down=matrix.length-1;
        while(true){
            for(int i=left;i<=right;i++){
                result.add(matrix[up][i]);
            }
            if(++up>down) break;

            for(int i=up;i<=down;i++){
                result.add(matrix[i][right]);
            }
            if(--right<left) break;

            for(int i=right;i>=left;i--){
                result.add(matrix[down][i]);
            }
            if(--down<up) break;

            for(int i=down;i>=up;i--){
                result.add(matrix[i][left]);
            }
            if(++left>right) break;
        }
        return result;
    }
}