검지week3

1. 체인 테이블 반전

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=NULL,*cur=head;
        while(cur)
        {
            auto next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
       while(!head||!head->next) return head;
       
       auto tail=reverseList(head->next);
       
       head->next->next=head;
       head->next=NULL;
       
       return tail;
    }
};

2. 체인 테이블 2개 결합

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto dummy=new ListNode(-1);
        auto cur=dummy;
        while(l1&&l2)
        {
            if(l1->valval)
            {
                cur->next=l1;
                cur=l1;
                l1=l1->next;
            }
            else
            {
                cur->next=l2;
                cur=l2;
                l2=l2->next;
            }
        }
        if(l1)cur->next=l1;
        else if(l2)cur->next=l2;
        return dummy->next;
    }  
};

3. 나무의 자 구조

class Solution {
public:
    bool hasSubtree(TreeNode* pRoot1,TreeNode* pRoot2) {
        if(!pRoot1||!pRoot2)    return false;
        if(ispart(pRoot1,pRoot2))   return true;
        return hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2);
    }
    bool ispart(TreeNode* pRoot1,TreeNode* pRoot2)
    {
        if(!pRoot2)return true;
        if(!pRoot1||pRoot1->val!=pRoot2->val) return false;
        return ispart(pRoot1->left,pRoot2->left)&&ispart(pRoot1->right,pRoot2->right);    
    }
};

4. 두 갈래 나무의 거울

class Solution {
public:
    void mirror(TreeNode* root) {
        if(!root)   return ;
        mirror(root->left);
        mirror(root->right);
        swap(root->left,root->right);
    }
};

5. 대칭적인 두 갈래 나무

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

6. 시계 방향으로 행렬 인쇄

class Solution {
public:
    vector printMatrix(vector > matrix) {
        vectorvt;
        if(matrix.empty()||matrix[0].size()==0)return vt;
        int n=matrix.size(),m=matrix[0].size();
        int book[n+5][m+5];
        memset(book,0,sizeof book);
        int tol=1,x=0,y=0;
        book[0][0]=1;
        vt.push_back(matrix[0][0]);
        while(tol=0&&book[x][y-1]==0)
            {
                vt.push_back(matrix[x][--y]);
                tol++;
                book[x][y]=1;
            }
            while(x-1>=0&&book[x-1][y]==0)
            {
                vt.push_back(matrix[--x][y]);
                tol++;
                book[x][y]=1;
            }
        }
        return vt;
    }
};

7. 메인이 포함된 창고

class MinStack {
public:
stackstk,min_stk;
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        if(stk.empty()|| min_stk.top()>=x)min_stk.push(x);
        stk.push(x);
    }
    
    void pop() {
        if(stk.top()==min_stk.top())min_stk.pop();
        stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return min_stk.top();
    }
};

8. 창고의 압축, 팝업 시퀀스

class Solution {
public:
    bool isPopOrder(vector pushV,vector popV) {
        if(pushV.size()!=popV.size())   return false;
        stackst;
        int i=0;
        for(auto x:pushV)
        {
            st.push(x);
            while(st.size()&&st.top()==popV[i])
            {
                st.pop();
                i++;
            }
        }
        return st.empty();
    }
};

9. 두 갈래 나무를 위에서 아래로 인쇄하지 않는다

class Solution {
public:
    vector printFromTopToBottom(TreeNode* root) {
        queueq;
        vectorvt;
        if(!root)return vt;
        q.push(root);
        while(!q.empty())
        {
            TreeNode* top=q.front();
            q.pop();
            vt.push_back(top->val);
            if(top->left)q.push(top->left);
            if(top->right)q.push(top->right);
        }
        return vt;
    }
};

10. 두 갈래 나무를 위에서 아래로 인쇄한다

class Solution {
public:
    vector> printFromTopToBottom(TreeNode* root) {
        queueq;
        vector>res;
        if(!root)   return res;
        q.push(root);
        while(!q.empty())
        {
            vectorcur;
            int n=q.size();// 
            for(int i=0;ival);
                if(top->left)q.push(top->left);
                if(top->right)q.push(top->right);
            }
            res.push_back(cur);
        }
        return res;
    }
};

11. 지그재그 인쇄 두 갈래 나무

class Solution {
public:
    vector> printFromTopToBottom(TreeNode* root) {
        int book=1;
        queueq;
        vector>res;
        if(!root)return res;
        q.push(root);
        while(!q.empty())
        {
            int n=q.size();
            vectorvt;
            for(int i=0;ival);
                if(top->left)
                    q.push(top->left);
                if(top->right)
                    q.push(top->right);
            }
            if(book==1)
                res.push_back(vt);
            else
            {
                reverse(vt.begin(),vt.end());
                res.push_back(vt);
            }
            book=-book;
        }
        return res;
    }
};