剑指offerWeek3
周六：栈的压入、弹出序列
题目链接：栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如序列 1,2,3,4,5
是某栈的压入顺序，序列 4,5,3,2,1
是该压栈序列对应的一个弹出序列，但 4,3,5,1,2
就不可能是该压栈序列的弹出序列。
注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。
数据范围
序列长度 [0,1000]
样例
输入：[1,2,3,4,5]
[4,5,3,2,1]
输出：true
AC代码
class Solution {
public:
bool isPopOrder(vector<int> pushV,vector<int> popV) {
if (pushV.size() != popV.size()) return false;
int idx = 0;
stack<int> stk;
for (auto x : pushV)
{
stk.push(x);
while (stk.size() && stk.top() == popV[idx])
{
idx ++ ;
stk.pop();
}
}
if (!stk.empty()) return false;
return true;
}
};
思路：
整体思路
模拟题
模拟的模板思路
当前可走的路径
- 路径1
- 路径2
...
- 路径n
可走路径的条件
- 条件1
- 条件2
...
- 条件n
对应本题：
当前可执行的操作(路径)
- 压栈
- 弹栈
压栈的条件：
- 栈为空的时候肯定可压
- 其他条件比较难想，先放着
弹栈的条件
- 当栈不空
- 只要栈顶元素和输出顺序的数值相同时，即弹
因此：
每次都压栈一次，然后只要栈不空且栈顶元素和输出顺序的数值相同时，就弹栈
周六：不分行从上往下打印二叉树
题目链接：不分行从上往下打印二叉树 文章来源：https://www.toymoban.com/news/detail-805932.html
从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。
数据范围
树中节点的数量 [0,1000]
。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
8
/ \
12 2
/
6
/
4
输出：[8, 12, 2, 6, 4]
AC代码
/**
* 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> printFromTopToBottom(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (q.size())
{
auto t = q.front();
q.pop();
res.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
return res;
}
};
思路：
整体思路文章来源地址https://www.toymoban.com/news/detail-805932.html
宽搜模板题
模板：
- 起点入队
- while (q.size())
{
- 队首出队
- 判断队首可达点
- 可达点入队
}
到了这里，关于剑指offer题解合集——Week3day6的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[wp]NewStarCTF 2023 WEEK3|WEB](https://imgs.yssmx.com/Uploads/2024/02/713593-1.png)
![力扣 [344、541、剑指offer 05.、151、剑指offer58-ll]](https://imgs.yssmx.com/Uploads/2024/02/616537-1.png)
