本文共 1707 字，大约阅读时间需要 5 分钟。

1. 栈的弹入、弹出序列

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

分析：要注意，千万别理解错了。别错误的认为，就一个栈，先进后出，我一下子全push进去，然后一下子全部pop出来！比如我push序列是1,2,3,4,5，那么我pop序列一定是 5,4,3,2,1。正确的理解应该是：可以先push几个进去，pop几个，然后再push几个，再继续pop，只要总的push序列是1,2,3,4,5，总的pop序列是想要的答案即可。

然后思考：我们需要一个辅助栈，帮助存储中间过程。pop的序列即为辅助栈的序列。所以，最后的终止条件是，如果辅助栈空了，说明pop序列是对的，要是辅助栈还有数字还有pop完，那就说明不是一个pop序列。思路如下：我们一直往辅助栈里面push pushV里面的元素，直到push到辅助栈的top()与popV的第一个元素相等，那就说明该pop了，这时候执行辅助栈的pop()即可，然后序列号加1，迭代计算后面的值。

代码如下：

bool IsPopOrder(vector
   
     pushV,vector
    
      popV) {     if(pushV.size() == 0 || popV.size() == 0 || pushV.size() != popV.size())         return false;    stack
     
       st;    int len = popV.size();    int popIndex = 0;    for(int i = 0; i < len; i++){        st.push(pushV[i]);        while(!st.empty() && popV[popIndex] == st.top()){            st.pop();            popIndex++;        }    }    return st.empty();}
     
    
   

2. 从上到下打印二叉树

题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。

分析：这题考查层序遍历！我们没有通用模板函数，所以只能自己构造。题目让我们从左到右，从上到下打印节点值，我们需要一个先入先出的数据结构，即queue。我们先把告诉根节点应该怎么做，然后按照我们之前提到的二叉树模板，左右递归即可。

那么根节点需要把自己的值push到vector中，然后pop，要保证每次front的值都是更新的！然后检查左右子树即可，比如说左子树，若是有左子树，即把左子树的结点push到队列中，然后检查到队列不为空，又会重复上面根节点的步骤。

代码如下：

vector
   
     PrintFromTopToBottom(TreeNode* root) {	if(root == nullptr)  return {}        queue
    
      q;    q.push(root);    TreeNode* node = nullptr;    vector
     
       ans;        while(!q.empty()){        node = q.front();        ans.push(node -> val);        q.pop();                if(node -> left) q.push(q->left);        if(node -> right) q.push(q->right);    }    return   ans;}
     
    
   

剑指offer第21,22 题

转载地址：https://blog.csdn.net/qq_45434780/article/details/115104586 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！