打卡

剑指26 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  };

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

    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        //判断当前树是否匹配，否则分别判断左右子树
        if(!A||!B)return false;
        return (is_match(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B));
    }
};

剑指27:二叉树镜像

#include<stack>
using namespace std;


class Solution {
      struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  };

public:
    TreeNode* mirrorTree_2(TreeNode* root) {
        //自下而上的过程
        if(!root)return nullptr;
        auto tmp = root->left;
        root->left = mirrorTree(root->right);
        root->right = mirrorTree(tmp);
        return root;
    }
    //用栈
     TreeNode* mirrorTree(TreeNode* root) {
         //自上而下的过程
        if(!root)return nullptr;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            auto top = st.top();st.pop();

            if(top->left)st.push(top->left);
            if(top->right)st.push(top->right);
            swap(top->left,top->right);
        }
        return root;
    }
};

对称二叉树

bool is_match(TreeNode* left,TreeNode* right){
        if(!left&&!right)return true;
        if(!left||!right||left->val!=right->val) return false;
        return is_match(left->left,right->right)&&is_match(left->right,right->left);
    }



    bool isSymmetric(TreeNode* root) {
        if(!root)return true;
        return is_match(root->left,root->right);
    }

30 最小栈

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

    }

    void push(int x) {
        st_1.push(x);
        if(x<=st_2.top())st_2.push(x);
    }

    void pop() {
        int val = st_1.top();
        st_1.pop();
        if(val==st_2.top())st_2.pop();
    }

    int top() {
        return st_1.top();
    }

    int min() {
        return st_2.top();
    }
};

31栈的压入序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

#include<vector>
#include<stack>

using namespace std;


class Solution {
public:
   bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0;
        for(auto num:pushed){
            //检查斩钉
            st.push(num);

            while(!st.empty()&&i<popped.size()&&st.top()==popped[i]){
                i++;
                st.pop();
            }
        }
        return st.empty();
    }
};

33 BST的后序遍历

#include<vector>

using namespace std;


class Solution {
public:
    bool is_match(vector<int>&postorder,int start,int end){
        if(start>=end)return true;
        int i = start;
        while(postorder[i]<=postorder[end])i++;
        int m = i;
        while(postorder[i]>postorder[end])i++;
        return i==end&&is_match(postorder,start,i-1)&&is_match(postorder,i,end-1);
    }

    bool verifyPostorder(vector<int>& postorder) {
        return is_match(postorder,0,postorder.size()-1);
    }
};