LeetCode力扣（剑指offer 26-30）26. 树的子结构 27. 二叉树的镜像 28. 对称的二叉树 29. 顺时针打印矩阵 30. 包含min函数的栈

剑指 Offer 26. 树的子结构

题解：

首先，排除其中一颗树为空树的情况。

递归A树，依次查找，如果有值等于B数的根节点时，开始比较A树和B树。如果直到B为空，说明B树和A树的子树相同，返回true。

代码：

class Solution {
public:
    bool recursion(TreeNode* A, TreeNode* B){
        if(B==nullptr)
            return true;
        if(A==nullptr||A->val!=B->val)
            return false;
        return recursion(A->left,B->left)&&recursion(A->right,B->right);
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==nullptr||B==nullptr)
            return false;
        return recursion(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);
    }
};

结果：

剑指 Offer 27. 二叉树的镜像

题解：

思想很简单，遍历二叉树的同时，交换其左右子节点。

节点交换时需要交换整个节点，而不是节点的值。

代码：

class Solution {
public:
    void swap(TreeNode* A){
        TreeNode *temp=A->left;
        A->left=A->right;
        A->right=temp;
    }
    void dfs(TreeNode* root){
        if(root==nullptr||(root->left==nullptr&&root->right==nullptr)) return;
        swap(root);
        dfs(root->left);
        dfs(root->right);
    }
    TreeNode* mirrorTree(TreeNode* root) {
        dfs(root);
        return root;
    }
};

结果：

剑指 Offer 28. 对称的二叉树

题解：

参考题26的思想，用递归去验证。

首先，设置结束条件，当a和b都为空指针时，说明是对称的。如果a和b只有一个为空，说明两边不对称，如果a和b的值不相等也是不对称的。

注意，递归时a和b一个指向左子树，一个指向右子树。

代码：

class Solution {
public:
    bool recursion(TreeNode* A, TreeNode* B){
        if(A==nullptr&&B==nullptr)
            return true;
        if((A!=nullptr&&B==nullptr)||(A==nullptr&&B!=nullptr)||(A->val!=B->val))
            return false;
        return recursion(A->left,B->right)&&recursion(A->right,B->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        return recursion(root->left,root->right);
    }
};

结果：

剑指 Offer 29. 顺时针打印矩阵

题解：

设置四个边界left,right,top,down分别表示矩阵的左右上下。

①先遍历第一行，遍历完之后top-1；

②遍历最后一列，遍历完后right-1；

③遍历最后一行，遍历完后down+1；

④遍历第一列，遍历完后left+1；

经过上面一轮后，最外围的一圈已经遍历完了，就会得到一个新矩阵，重复上述步骤。

代码：

public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int i=0;
        if(matrix.size()==0)  return res;
        int left=0,right=matrix[0].size()-1,top=0,down=matrix.size()-1;
        while(1){
            i=left;
            while(i<=right)res.push_back(matrix[top][i++]);
            if(top==down) break;
            ++top;

            i=top;
            while(i<=down) res.push_back(matrix[i++][right]);
            if(right==left) break;
            --right;

            i=right;
            while(i>=left) res.push_back(matrix[down][i--]);
            if(down==top) break;
            --down;

            i=down;
            while(i>=top) res.push_back(matrix[i--][left]);
            if(left==right)break;
            ++left;
        }
        return res;
    }
};

结果：

剑指 Offer 30. 包含min函数的栈

题解：

设置两个栈，一个用来正常存储，一个用来按从底向上从大到小存储顺序存储。

所以只需要在push函数做文章，对于顺序栈，当前值比栈顶元素小，说明最小值还是栈顶元素，就把当前值压入栈中；如果不是，就继续把栈顶元素压入栈中。

两个栈元素个数时一样的，所以可以同步出栈。

代码：

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> T;
    stack<int> Tmin;
    MinStack() {

    }
    
    void push(int x) {
        T.push(x);
        if(Tmin.empty())
            Tmin.push(x);
        else
            Tmin.push(x<Tmin.top()?x:Tmin.top());
    }
    
    void pop() {
        Tmin.pop();
        T.pop();
    }
    
    int top() {
        return T.top();
    }
    
    int min() {
        return Tmin.top();
    }
};

结果：