4.2画图让抽象问题形象化
二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
//利用递归
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null)
            return;
        if(root.left==null && root.right==null)
            return;
        TreeNode t=root.left;
        root.left=root.right;
        root.right=t;
        if(root.left!=null)
            Mirror(root.left);
        if(root.right!=null)
            Mirror(root.right);
    }
}

对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
示例1
输入：{8,6,6,5,7,7,5}
返回值：true

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
//利用递归
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot==null)
            return true;
        return Mirror(pRoot.left,pRoot.right);
    }
    boolean Mirror(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;
        else
            return Mirror(left.left,right.right)&&Mirror(left.right,right.left);
    }
}

顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.
示例1
输入：[[1,2],[3,4]]
返回值：[1,2,4,3]

//判断条件1
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        ArrayList<Integer> a=new ArrayList<>();
        int start=0;
        while(2*start<row&&2*start<col)
        {
            a=printOne(start,row,col,a,matrix);
            start++;
        }
        return a;
    }
    public ArrayList<Integer> printOne(int start,int row,int col,ArrayList a,int [][] matrix)
    {
        int r=row-start-1;
        int c=col-start-1;
        for(int i=start;i<=c;i++)
        {
            a.add(matrix[start][i]);
        }
        for(int i=start+1;i<=r;i++)
        {
            a.add(matrix[i][c]);
        }
        for(int i=c-1;i>=start&&r!=start;i--)
        {
            a.add(matrix[r][i]);
        }
        for(int i=r-1;i>start&&c!=start;i--)
        {
            a.add(matrix[i][start]);
        }
        return a;
    }
}
//判断条件2
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       ArrayList<Integer> a=new ArrayList<>();
        int m=matrix.length;
        int n=matrix[0].length;
        int top=0,left=0,right=n-1,bottom=m-1;
        while(top<=bottom&&left<=right)
        {
            for(int i=left;i<=right;i++)
                a.add(matrix[top][i]);
            for(int i=top+1;i<=bottom;i++)
                a.add(matrix[i][right]);
            for(int i=right-1;i>=left && top<bottom;i--)
                a.add(matrix[bottom][i]);
            for(int i=bottom-1;i>top && right>left;i--)
                a.add(matrix[i][left]);
            top++;left++;right--;bottom--;
        }
        return a;
    }
}

测试用例
矩阵有n行n列；矩阵有n行m列；矩阵只有1行；矩阵只有1列；矩阵只有1行1列。

4.3举例让抽象问题具体化
包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。

//利用辅助栈存储此时栈中的最小元素，辅助栈顶元素即为此时栈中的最小元素。
import java.util.Stack;
public class Solution {
    Stack<Integer> s=new Stack<>();
    Stack<Integer> m=new Stack<>();
    int min;
    public void push(int node) {
        s.push(node);
        if(m.empty()||min>node)
        {
            min=node;
            m.push(node);
        }
        else
            m.push(min);
    }
    public void pop() {
        //辅助栈应始终和该栈的高度保持一致
        s.pop();
        m.pop();
    }
    public int top() {
        return s.peek();
    }
    public int min() {
        return m.peek();
    }
}

栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
示例1
输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false

//列举每一种可能出现的情况
import java.util.Stack;
public class Solution {
    Stack<Integer> s=new Stack<>();
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int i=0,j=0;
        while(j<popA.length)
        {
            if(i<pushA.length && pushA[i]==popA[j])
            {
                i++;
                j++;
            }
            else if(!s.isEmpty() && s.peek()==popA[j])
            {
                s.pop();
                j++;
            }
            else if(i<pushA.length && pushA[i]!=popA[j])
            {
                s.push(pushA[i]);
                i++;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
}
//简洁方法
import java.util.Stack;
public class Solution {
    Stack<Integer> s=new Stack<>();
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int index=0;
        Stack<Integer> s=new Stack<>();
        for(int i=0;i<pushA.length;i++)
        {
            s.push(pushA[i]);
            while(!s.isEmpty()&&s.peek()==popA[index])
            {
                index++;
                s.pop();
            }
        }
        return  s.isEmpty();
    }
}