4/5剑指offer

1.二叉树的镜像
思路：先前序遍历树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶子节点的左、右子节点之后，就得到了树的镜像。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot==nullptr)
            return;
        if(pRoot->left==nullptr&&pRoot->right==nullptr)
            return;//左右子树都为null才返回
        TreeNode *temp=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=temp;//交换左右子树
        if(pRoot->left)
            Mirror(pRoot->left);//递归交换左子树
        if(pRoot->right)
            Mirror(pRoot->right);//递归交换右子树

    }
};

2.对称的二叉树（如果与树的镜像相等说明此树是对称的）
思路：通过比较二叉树的前序遍历和对称前序遍历来判断二叉树是否对称，注意要包含nullptr的子节点。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        return judge(pRoot,pRoot);             
    }
    bool judge(TreeNode* pRoot1,TreeNode* pRoot2)
    {
        if(pRoot1==nullptr&&pRoot2==nullptr)
            return true;
        if(pRoot1==nullptr||pRoot2==nullptr)
            return false;
        if(pRoot1->val!=pRoot2->val)
            return false;
        return judge(pRoot1->left,pRoot2->right)&&judge(pRoot1->right,pRoot2->left);
    }
};

3.顺时针打印矩阵
(1):我们可以发现左上角的坐标中行标和列标总是相同的，于是可以在矩阵中选取左上角为（start，start）的一圈作为分析的目标。可以发现，循环的条件是列与行都大于start×2；
(2)：打印一圈需要检查的内容，第一步（从左到右）一定是需要的，第二步执行的前提条件是终止行号要大于起始行号，第三步的执行条件是圈内至少有两行两列，也就是说要要求终止行号大于起始行号，终止列号也要大于起始列号，第四步的执行条件是至少有三行两列，因此要求终止行号比起始行号至少大2，同时终止列号大于起始列号。

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int start=0;     
        vector<int> result;
        if(matrix.size()==0||matrix[0].size()==0) return result;
        int row=matrix.size();//行
        int col=matrix[0].size();//列
        while(row>start*2&&col>start*2)
        {
            print(row,col,start,result,matrix);
            start++;//决定打印几圈
        }
        return result;
    }
    void print(int row,int col,int start,vector<int> &result,vector<vector<int> > &matrix)
    {
        int endX=col-1-start;//横坐标,x轴，横向
        int endY=row-1-start;//纵坐标，y轴，纵向
        for(int i=start;i<=endX;i++)
        {
            result.push_back(matrix[start][i]);//第一行从左往右
        }
        if(endY>start)
        {
            for(int i=start+1;i<=endY;i++)
            {
                result.push_back(matrix[i][endX]);//最后一列从上往下
            }
        }
        if(endX>start&&endY>start)
        {
            for(int i=endX-1;i>=start;i--)
            {
                result.push_back(matrix[endY][i]);//最后一行从左往右
            }
        }
        if(endX>start&&endY>start+1)
        {
            for(int i=endY-1;i>=start+1;i--)
            {
                result.push_back(matrix[i][start]);//最后一列从下往上
            }
        }
    }
};