一周刷完剑指offer(3)

day3

22.链表中倒数第k个节点

思路1:遍历链表两次，第一次统计处链表中节点的个数，第二次找到倒数第k个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        int num=0;
        ListNode* cur=head;
        while(cur){
            num++;
            cur=cur->next;
        }
        cur=head;
        int p=0;
        while(cur){
            if(p==num-k){
                break;
            }
            cur=cur->next;
            p++;
        }
        return cur;
    }
};

思路2:只遍历一次，但是边遍历边保存

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        vector<ListNode*> res;
        while(head){
            res.push_back(head);
            head=head->next;
        }
        return res[res.size()-k];
    }
};

ps该段代码不够robust,需要考虑head为空，k的数目为0，k的数目大于节点的总数的情况。思路三自己的代码比较robust，面对这三种情况都可以过。

思路3:只遍历一次
定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个指针到达链表的尾节点时，第二个指针正好指向倒数第k个节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* pre=head,*cur=head;
        int count=0;
        while(cur){
            cur=cur->next;
            count++;
            if(count>k){
                pre=pre->next;
            }
        }
        return pre;
    }
};

总结：当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。

23.链表中环的入口节点(重点)

题目:如果一个链表中包含环，如何找出环的入口节点？
思路:p139
代码:没有写 下次自己写写看

24.反转链表(重点)

思路1:先找到最后一个节点，修改它的next；然后又从头遍历，修改反转链表的第二个节点的next，不断从头遍历，直到修改完所有节点的next。
写完之后感觉到可以改写成递归的形式。不断return当前子问题的最后一个节点。
时间效率超级低

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* newHead=head,*cur=head,*pre=head;
        if(head==NULL || head->next==NULL){
            return head;
        }
        while(cur->next!=NULL){
            cur=cur->next;
        }
        newHead=cur;
        while(cur!=head){
            while(pre->next!=cur){
                pre=pre->next;
            }
            cur->next=pre;
            cur=pre;
            pre=head;
        }
        cur->next=NULL;
        return newHead;
    }
};

思路2:遍历的时候顺便记住当前节点的前驱节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur=head;
        if(head==NULL || head->next==NULL){
            return head;
        }
        vector<ListNode*> add;
        while(cur->next!=NULL){
            add.push_back(cur);
            cur=cur->next;
        }
        head=cur;
        for(int i=add.size()-1;i>=0;i--){
            cur->next=add[I];
            cur=add[I];
        }
        cur->next=NULL;
        return head;
    }
};

思路3:递归

  • 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作ret
  • 此后，每次函数在返回的过程中，让当前结点的下一个结点的next 指针指向当前节点
  • 同时让当前结点的next 指针指向NULL ，从而实现从链表尾部开始的局部反转

  • 当递归函数全部出栈后，链表反转完成



    仔细推敲、实现下述代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
};

思路4:三指针(迭代)
课本p143(绝了)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL || head->next==NULL){
        //其实if(head==NULL){就可以了
            return head;
        }
        ListNode* pre=NULL,*cur=head,*next;//pre要设置成null!!
        while(cur){
            next=cur->next;
            cur->next=pre;//pre设置成null的原因在这里
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

思路5:妖魔化的双指针

  • 原链表的头结点就是反转之后链表的尾结点，使用head 标记 .
  • 定义指针cur，初始化为head .
  • 每次都让head 下一个结点的next 指向cur ，实现一次局部反转
  • 局部反转完成之后，cur 和 head 的next 指针同时 往前移动一个位置

  • 循环上述过程，直至cur 到达链表的最后一个结点 .



    代码:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL) { return NULL; }
        ListNode* cur = head;
        while (head->next != NULL) {
            ListNode* t = head->next->next;
            head->next->next = cur;
            cur = head->next;
            head->next = t;
        }
        return cur;
    }
};

总结:
涉及到链表的操作，一定要在纸上把过程先画出来，再写程序。

25.合并两个排序的链表

思路1:每个链表有一个指针，同时遍历，然后慢慢构建新链表。
自己写的复杂代码,本不必这么复杂，而且也不用不断new新的节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL && l2==NULL){
            return NULL;
        }
        ListNode *head=new ListNode();
        ListNode *temp=head,*pre=NULL;
        while(l1 || l2){
            if(l1 && l2 && (l1->val < l2->val)){
                temp->val=l1->val;
                temp->next=NULL;
                l1=l1->next;
                if(pre!=NULL){
                    pre->next=temp;
                }
                pre=temp;
                temp=new ListNode();
            }
            else if(l1 && l2 && (l1->val > l2->val)){
                temp->val=l2->val;
                temp->next=NULL;
                l2=l2->next;
                if(pre!=NULL){
                    pre->next=temp;
                }
                pre=temp;
                temp=new ListNode();
            }
            else if(l1 && l2 && (l1->val == l2->val)){
                ListNode *temp2=new ListNode;
                temp->val=l2->val;
                temp->next=temp2;
                temp2->val=l2->val;
                temp2->next=NULL;
                l1=l1->next;
                l2=l2->next;
                if(pre!=NULL){
                    pre->next=temp;
                }
                pre=temp2;
                temp=new ListNode();
            }
            else if(l1 && !l2){
                while(l1){
                    temp->val=l1->val;
                    temp->next=NULL;
                    if(pre!=NULL){
                        pre->next=temp;
                    }
                    pre=temp;
                    temp=new ListNode();
                    l1=l1->next;

                }
            }
            else if(!l1 && l2){
                while(l2){
                    temp->val=l2->val;
                    temp->next=NULL;
                    if(pre!=NULL){
                        pre->next=temp;
                    }
                    pre=temp;
                    temp=new ListNode();
                    l2=l2->next;
                }
            }

        }
        return head;
    }
};

理清思路之后，再度修改。
清晰思路：
非常清晰，重点在解题思路和算法流程
https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/solution/mian-shi-ti-25-he-bing-liang-ge-pai-xu-de-lian-b-2/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummyHead=new ListNode(),*pre=dummyHead;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val <= l2->val) {
                pre->next = l1;
                pre = pre->next;
                l1 = l1->next;
            } else {
                pre->next = l2;
                pre = pre->next;
                l2 = l2->next;
            }
        }
        if (l1 != NULL) {
            pre->next = l1;
        }
        if (l2 != NULL) {
            pre->next = l2;
        }
        return dummyHead->next;
    }
};

思路2:递归(绝了，我怎么没想到)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL){
            return l2;
        }
        else if(l2==NULL){
            return l1;
        }
        ListNode* pMergeHead=NULL;
        if(l1->val<l2->val){
            pMergeHead=l1;
            pMergeHead->next=mergeTwoLists(l1->next,l2);
        }
        else{
            pMergeHead=l2;
            pMergeHead->next=mergeTwoLists(l1,l2->next);
        }
        return pMergeHead; 
    }
};

26.树的子结构(重点)

不会写
首先理解子结构的意思。
而且题目的输入是两个TreeNode*，不要想成输入是层序遍历，纠结着没有给出树的具体结构，还想着自己根据序列造树。
思路1:p148
根据思路，写了代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==NULL||B==NULL){
            return false;
        }
        if(A->val==B->val){
            if(isSub(A,B)){
                return true;//一开始不对，不能就急着返回false;有可能后面子结构才相同。
            }
        }
        return (isSubStructure(A->left,B)||isSubStructure(A->right,B));
    }

    bool isSub(TreeNode* A, TreeNode* B){
        if(B==NULL){
            return true;
        }
        else if(A==NULL){//不然后面可能出现A空指针的错误,因为用了A->val
            return false;
        }
        if(B->val!=A->val){
            return false;
        }
        return (isSub(A->left,B->left)&&isSub(A->right,B->right));
    }
};

别人的代码

public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (A == null || B == null)
        return false;
    //先从根节点判断B是不是A的子结构，如果不是在分别从左右两个子树判断，
    //只要有一个为true，就说明B是A的子结构
    return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}

boolean isSub(TreeNode A, TreeNode B) {
    //这里如果B为空，说明B已经访问完了，确定是A的子结构
    if (B == null)
        return true;
    //如果B不为空A为空，或者这两个节点值不同，说明B树不是
    //A的子结构，直接返回false
    if (A == null || A.val != B.val)
        return false;
    //当前节点比较完之后还要继续判断左右子节点
    return isSub(A.left, B.left) && isSub(A.right, B.right);
}

27.二叉树的镜像(重点)

思路1:递归
求树的镜像的过程其实就是在遍历树的同时交换非叶节点的左、右子节点!!!

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* root){
        if(root==NULL){
            return;
        }
        TreeNode* temp=root->left; //为什么temp=root不行?
        root->left=root->right;
        root->right=temp;
        dfs(root->left);
        dfs(root->right);
    }
};

其实不需要再写个dfs的，你的递归还不够熟练。

TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return root;
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==NULL){
            return root;
        }
        TreeNode* temp=root->left; //temp=root不行,这样之后temp就是root了呀～
        root->left=mirrorTree(root->right);
        root->right=mirrorTree(temp);
        return root;
    }
};

思路2:迭代
利用栈（或队列）遍历树的所有节点 node ，并交换每个 node 的左 / 右子节点。
算法流程：
特例处理： 当 root 为空时，直接返回 null ；
初始化： 栈（或队列），加入根节点 root 。
循环交换： 当栈 stack 为空时跳出；
出栈： 记为 node ；
添加子节点： 将 node 左和右子节点入栈；
交换： 交换 node 的左 / 右子节点。
返回值： 返回根节点 root 。

    // 栈
    TreeNode* mirrorTree(TreeNode* root) {
        stack<TreeNode*> sck;
        sck.push(root);
        while(!sck.empty())
        {
            TreeNode* tmp = sck.top();
            sck.pop();
            if(!tmp) continue;
            swap(tmp->left,tmp->right);
            if(tmp->right != NULL) sck.push(tmp->right);
            if(tmp->left != NULL) sck.push(tmp->left);
        }
        return root;
    }
    // 队列
    TreeNode* mirrorTree(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            TreeNode* tmp = que.front();
            que.pop();
            if(tmp == NULL) continue;
            swap(tmp->left,tmp->right);
            if(tmp->left) que.push(tmp->left);
            if(tmp->right) que.push(tmp->right);
        }
        return root;
    }

28.对称的二叉树

错误思路:中序遍历，看看遍历的结果是否以根节点为中心左右对称。
出错的case:
[1,2,2,2,null,2] false
[] true
[5,4,1,null,1,null,4,2,null,2,null] false
反思：经过第一个false之后，决定把null也记录，可是思维还是有漏洞。或许是因为中序遍历不能确定一个树吧。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==NULL){
            return true;//一般null都是return false，但是这题不一样。
        }
        vector<char> node;
        dfs(root,node);
        int len=node.size();
        if(len%2){
            for(int i=0;i<len/2;i++){
                if(node[i]!=node[len-i-1]){
                    return false;
                }
            }
            return true;
        }
        else{
            return false;
        }
    }

    void dfs(TreeNode* root,vector<char> &node){
        if(root==NULL){
            return;
        }
        
        if(root->left == NULL && root->right != NULL){
            node.push_back('*');
        }
        dfs(root->left,node);

        node.push_back(root->val);

        if(root->left != NULL && root->right == NULL){
            node.push_back('*');
        }
        dfs(root->right,node);
    }
};

思路2：
对称也就意味着左右两边一致。
那么我同时执行两个中序遍历:左根右以及右根左，判断节点值是否一致。
利用遍历解决树的问题。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return dfs(root,root);
    }

    bool dfs(TreeNode* root1,TreeNode* root2){
        bool res=false;
        if(root1==NULL && root2==NULL){
            return true;
        }
        else if(!root1||!root2){ //有一个为空
            return false;
        }
        res=dfs(root1->left,root2->right);
        if(root1->val!=root2->val){
            return false;
        }
        if(res){
            res=dfs(root1->right,root2->left);
        }
        return res;
    }
};

本质上，前中后序遍历都可以解决问题。
前序遍历思路、代码参考课本p160

思路3:

  • 采用层序遍历的方式，先将每层的节点值保持到一个vector容器中
  • 每遍历一层就采用"双指针”的方法对vector容器的值进行对称判断，若不满足直接返回false
  • 直到遍历完所有节点
    自己没有去实现:
class Solution {
public:
    bool bfs(TreeNode* root){
        if(root==nullptr)   return true;
        queue<TreeNode*> Q;
        Q.push(root);
        vector<int> ivec;
        while(!Q.empty()){
            auto sz = Q.size();
            if(sz>1 && sz%2)    return false;        //该层数量不对称
            if(ivec.size() > 1){
                for(int i=0;i<ivec.size();++i){
                    if(ivec[i] != ivec[ivec.size()-1-i])
                        return false;
                }
                ivec.clear();
            }
            while(sz--){
                auto rt = Q.front();
                Q.pop();
                if(rt->left){
                    Q.push(rt->left);
                    ivec.push_back(rt->left->val);
                }
                else ivec.push_back(-1);     //空节点的值默认为-1
                
                if(rt->right){
                    Q.push(rt->right);
                    ivec.push_back(rt->right->val);
                }
                else ivec.push_back(-1);     //空节点的值默认为-1
            }
        }
        return true;
    }
    bool isSymmetric(TreeNode* root) {
        return bfs(root);
    }
};

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root){
            return true;
        }
        queue<TreeNode *> que1;
        que1.push(root);
        while(!que1.empty()){
            int size = que1.size();
            vector<TreeNode *> tmp;
            while(size > 0){
                TreeNode *fronts = que1.front();
                que1.pop();
                tmp.push_back(fronts->left);
                if(fronts->left){
                    que1.push(fronts->left);
                }
                tmp.push_back(fronts->right);
                if(fronts->right){
                    que1.push(fronts->right);
                }
                size --;
            }
            int i=0;
            int j=tmp.size()-1;
            while(i<j){
                if(tmp[i] != nullptr && tmp[j] != nullptr){
                    if(tmp[i]->val != tmp[j]->val){
                        return false;
                    }
                }
                else if(tmp[i] == nullptr && tmp[j] == nullptr){
                }
                else{
                    return false;
                }
                i++;
                j--;
            }
        }
        return true;
    }
};

bool isSymmetric(TreeNode* root) {
        bool ans = true;
        vector<pair<TreeNode*, TreeNode*>> buffer;

        if(root != nullptr) 
            buffer.push_back({root->left, root->right});
        
        TreeNode *lhs,*rhs;
        while(!buffer.empty())
        {
            tie(lhs, rhs) = buffer.back(); buffer.pop_back();

            if(lhs == nullptr && rhs == nullptr) continue;
            if(lhs == nullptr || rhs == nullptr) return false;
            if(lhs->val != rhs->val) return false;

            buffer.push_back({rhs->right,lhs->left});
            buffer.push_back({rhs->left, lhs->right});
        }
        return ans;
    }

思路4:迭代法
https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/solution/dui-cheng-er-cha-shu-di-gui-fa-die-dai-fa-xiang-ji/
https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/solution/cyu-pythonliang-chong-jie-fa-shi-xian-di-gui-yu-di/
不是层序遍历，而是利用栈/队列将递归算法实现。

29.顺时针打印矩阵

ps：矩阵不一定是方阵
思路1：静下心来，分析打印路径：往右、往下、往左、往上，这四条路的边界情况。最后测试特殊情况：只有一行、一列、空矩阵，将代码修改得更robust。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.size()==0 || matrix[0].size()==0){
            return ans;
        }
        int up_b=0,down_b=matrix.size()-1,left_b=0,right_b=matrix[0].size()-1;
        //b为bound
        while(up_b<=down_b && left_b<=right_b){
            for(int j=left_b;j<=right_b;j++){
                ans.push_back(matrix[up_b][j]);
            }
            up_b++;
            for(int i=up_b;i<=down_b;i++){
                ans.push_back(matrix[i][right_b]);
            }
            right_b--;
            for(int j=right_b;up_b<=down_b && j>=left_b;j--){
                ans.push_back(matrix[down_b][j]);
            }
            down_b--;
            for(int i=down_b;right_b>=left_b && i>=up_b;i--){
                ans.push_back(matrix[i][left_b]);
            }
            left_b++;
        }
        return ans;
    }
};

其他人同样的思路，但感觉更清晰
https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/mian-shi-ti-29-shun-shi-zhen-da-yin-ju-zhen-she-di/
注意理解上面这条链接的思路。为什么人家break。

https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/shun-shi-zhen-da-yin-ju-zhen-by-leetcode-solution/

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector <int> res;
        if(matrix.empty()|| matrix[0].size()==0) return res;
        int rl = 0, rh = matrix.size()-1; //记录待打印的矩阵上下边缘
        int cl = 0, ch = matrix[0].size()-1; //记录待打印的矩阵左右边缘
        while(1){
            for(int i=cl; i<=ch; i++) res.push_back(matrix[rl][i]);//从左往右
            if(++rl > rh) break; //若超出边界，退出
            for(int i=rl; i<=rh; i++) res.push_back(matrix[i][ch]);//从上往下
            if(--ch < cl) break;
            for(int i=ch; i>=cl; i--) res.push_back(matrix[rh][i]);//从右往左
            if(--rh < rl) break;
            for(int i=rh; i>=rl; i--) res.push_back(matrix[i][cl]);//从下往上
            if(++cl > ch) break;
        }
        return res;
    }
};

思路2:课本的思路p161感觉略复杂

30.包含min函数的栈(重点)

不会写
思路：把最小元素用另外的辅助栈保存
p165-168

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    stack<int> min_s;
    MinStack() {
        while(!s.empty()){
            s.pop();
        }
        while(!min_s.empty()){
            min_s.pop();
        }
    }
    
    void push(int x) {
        s.push(x);
        if(min_s.size()==0 || x<min_s.top()){ //非常重要!
            min_s.push(x);
        }
        else{
            min_s.push(min_s.top());
        }
    }
    
    void pop() {
        s.pop();
        min_s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        return min_s.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */

类似思路:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/
变化在于min栈只存入stack top对应的 新的 最小值，若不变，则不存。

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    stack<int> min_s;
    MinStack() {
        while(!s.empty()){
            s.pop();
        }
        while(!min_s.empty()){
            min_s.pop();
        }
    }
    
    void push(int x) {
        s.push(x);
        if(min_s.size()==0 || x<=min_s.top()){ //<=!! 因为又可能有同样的值都是最小 入栈
            min_s.push(x);
        }
    }
    
    void pop() {
        if(s.top()==min_s.top()){
            min_s.pop();
        }
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        return min_s.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */

31.栈的压入弹出序列(重点)

不会写
思路1:p168-170

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.empty()&&popped.empty()){
            return true;
        }
        else if(pushed.empty()||popped.empty()){
            return false;
        }
        
        stack<int> s;
        int j=0;//index in pushed;
        for(int i=0;i<popped.size();i++){
            if(s.empty()|| s.top()!=popped[i]){
                for(;j<pushed.size()&&pushed[j]!=popped[i];j++){
                    s.push(pushed[j]);
                }
                if(j==pushed.size()){
                    break;
                }
                else{
                    s.push(pushed[j++]);
                }
            }
            if(s.top()==popped[i]){
                s.pop();
            }
        }

        if(s.empty()){
            return true;
        }
        else{
            return false;
        }
    }
};

按照课本的代码，修改了自己的代码

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.empty()&&popped.empty()){
            return true;
        }
        else if(pushed.empty()||popped.empty()){
            return false;
        }

        stack<int> s;
        int i=0,j=0;//pointer in popped and pushed;
        for(;i<popped.size();i++){
            while(s.empty()|| s.top()!=popped[i]){
                if(j==pushed.size()) break;
                s.push(pushed[j++]);
            }
            if(s.top()!=popped[i]){
                break;
            }
            s.pop();
        }

        if(s.empty()){
            return true;
        }
        else{
            return false;
        }
    }
};

思路2:
判断合不合法，用个栈试一试:
把压栈的元素按顺序压入，当栈顶元素和出栈的第一个元素相同，则将该元素弹出，出栈列表指针后移并继续判断。
最后判断出栈列表指针是否指向出栈列表的末尾即可/或者判断辅助栈是否为空。

 public boolean validateStackSequences(int[] pushed, int[] popped) {

        Deque<Integer> stack = new ArrayDeque();
        int j = 0;
        for (int elem : pushed) {
            stack.push(elem);
            while (j < popped.length && !stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return j == popped.length;
    }

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    stack<int>st;
    int cur=0;
    for(int i=0;i<pushed.size();++i)
    {
        st.push(pushed[i]);
        while(!st.empty()&&st.top()==popped[cur])
        { 
            st.pop();
            ++cur;
        }
    }
        return st.empty();
    }

32.从上到下打印二叉树 I

思路：二叉树层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<int> ans;
        if(root==NULL){
            return ans;
        }
        q.push(root);
        while(!q.empty()){
            TreeNode *temp=q.front();
            ans.push_back(temp->val);
            if(temp->left!=NULL){
                q.push(temp->left);
            }
            if(temp->right!=NULL){
                q.push(temp->right);
            }
            q.pop();
        }
        return ans;
    }
};

32 - II 从上到下打印二叉树 II (重点)

不会写
自己的复杂思路：记录下每一个节点的层号，根据层号完成题目要求的分层输出任务。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        vector<int> per_level_ans;
        if(root==NULL){
            return ans;
        }
 
        queue<TreeNode*> q;
        q.push(root);

        vector<int> level;
        level.push_back(0);
        int cur=0;

        while(!q.empty()){
            TreeNode *temp=q.front();
            q.pop();
            per_level_ans.push_back(temp->val);
            if(temp->left!=NULL){
                q.push(temp->left);
                level.push_back(level[cur]+1);
            }
            if(temp->right!=NULL){
                q.push(temp->right);
                level.push_back(level[cur]+1);
            }
            if(cur==level.size()-1 || level[cur]!=level[cur+1]){ //注意防止越界
                ans.push_back(per_level_ans);
                per_level_ans.clear();
            }
            cur++;
        }
        return ans;
    }
};

思路2:
p174-175
关键在于定义两个变量：当前层中还没有打印的节点数；下一层节点的数目。
因为并没有必要记录下每个节点处在的层次！

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        vector<int> per_level_ans;
        if(root==NULL){
            return ans;
        }
 
        queue<TreeNode*> q;
        q.push(root);

        int toBePrinted=1;
        int nextLevel=0;
        while(!q.empty()){
            TreeNode *temp=q.front();
            q.pop();
            per_level_ans.push_back(temp->val);
            toBePrinted--;
            if(temp->left!=NULL){
                q.push(temp->left);
                nextLevel++;
            }
            if(temp->right!=NULL){
                q.push(temp->right);
                nextLevel++;
            }
            if(toBePrinted==0){
                ans.push_back(per_level_ans);
                per_level_ans=vector<int> ();//per_level_ans.clear();
                toBePrinted=nextLevel;
                nextLevel=0;
            }
        }
        return ans;
    }
};

思路3:
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5/
太巧妙了。关键在于：将本层全部节点打印到一行，并将下一层全部节点加入队列。


class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

与上面类似的思路，只是for循环不同写法。感受一下！

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        List<Integer> tmp = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                root = queue.poll();
                tmp.add(root.val);
                if (root.left != null) {
                    queue.add(root.left);
                }
                if (root.right != null) {
                    queue.add(root.right);
                }
            }
            ret.add(new ArrayList<>(tmp));
            tmp.clear();
        }
        return ret;
    }
}

递归

public class Solution {
    private List<List<Integer>> ret;

    public List<List<Integer>> levelOrder(TreeNode root) {
        ret = new ArrayList<>();
        dfs(0, root);
        return ret;
    }

    private void dfs(int depth, TreeNode root) {
        if (root == null) {
            return;
        }
        if (ret.size() == depth) {
            ret.add(new ArrayList<>());
        }
        ret.get(depth).add(root.val);
        dfs(depth + 1, root.left);
        dfs(depth + 1, root.right);
    }
}

32 - III 从上到下打印二叉树 III

思路：模仿题目2的思路3做法，增加奇偶层的处理即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        vector<int> per_level_ans;
        if(root==NULL) return ans;
        
        queue<TreeNode*> q;
        q.push(root);
        int level=0;
        while(!q.empty()){
            for(int i=q.size();i>0;i--){
                TreeNode* temp=q.front();
                q.pop();
                per_level_ans.push_back(temp->val);
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
            }
            if(level&1){//奇数
                //reverse(per_level_ans.begin(),per_level_ans.end());
                per_level_ans=vector<int>(per_level_ans.rbegin(), per_level_ans.rend());
                //两个方法都可以，下面那个是反向迭代器
            }
            ans.push_back(per_level_ans);
            per_level_ans.clear();
            level++;
        }
        return ans;
    }
};

思路2:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er--3/
没有细看和实现，主要是使用了双端队列。
该思路下面的评论有递归，也没看。
快速看懂代码/思路的方法：找个实例，跟着程序走一遍。
ps：双端队列时，addFirst是加在队头，后进先出，和栈类似。 addLast是加在队尾，先进先出，和队列类似。
课本p176-179 与该思路2基本一致，同样没有动手实现。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,588评论 6赞 496
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,456评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,146评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,387评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,481评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,510评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,522评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,296评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,745评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,039评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,202评论 1赞 343
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,901评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,538评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,165评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,415评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,081评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,085评论 2赞 352