一、按Z形层序遍历二叉树
1.链接
103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）
2.描述
按照Z字形去层序遍历（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）
3.思路
首先，我们知道对于一个二叉树的层序遍历，是利用队列的特性，将节点依次放入队列去完成的，并且可以通过一个整形去记录每一层有多少个节点，实现按层输出
而这题要求Z形输出，我们可以认为就是相对于上一层，当前层一定是相反的顺序输出，逆序的输出我们想到可以利用栈先进后出的特性，但是由于栈会被压栈，所以在记录下一层子节点的时候，我们不能直接用栈去记录，而是用一个辅助队列是存放下一层的数据，并且，我们需要判断当前层的顺序是左到右，还是右到左，以此来确定入队列时是先入那一个子树
4.参考代码
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;
if (root == nullptr) {
return ret;
}
stack<TreeNode*> s;
queue<TreeNode*> date;//用来存放数据的辅助队列
int state = 1;//状态值：状态为1则表示当前从左到右，负责表示从右到左
s.push(root);
while(!s.empty() || !date.empty())
{
vector<int> tmp;
//首先是把栈中的元素，即某一层的元素遍历
while(!s.empty())
{
TreeNode* cur = s.top();
s.pop();
tmp.push_back(cur->val);
TreeNode* first = state == 1 ? cur->left:cur->right;
TreeNode* second = state == 1? cur->right : cur->left;
if(first)
{
date.push(first);
}
if(second)
{
date.push(second);
}
}
ret.push_back(tmp);
while(!date.empty())//此时检查保存的数据，若有数据要依次入栈进行遍历，并且改变方向
{
s.push(date.front());
date.pop();
}
state^=1;//改变方向
}
return ret;
}
};5.代码分析
二、搜索二叉树中第K个小的元素
1.链接
230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）
2.描述
找到搜索二叉树中，第k个小的元素
3.思路
（1）递归
这里可以使用递归去找，根据搜索二叉树的特性，中序遍历就是一个升序的结果,我们只需要通过递归到第k个的时候，将数据记录返回即可
（2）循坏
除了使用递归的方式去利用搜索二叉树的特性去找之外，还可以使用循坏的方式去模拟中序递归的办法，利用一个栈去实现，这个在实现上相对复杂一点
首先我们需要一个栈，去对每一个节点，先是走左节点，从根开始将左边节点都入栈，直到遇到左边为空时，则此时栈顶的元素就是当前要访问的节点，将其出栈，并且还需要去继续走它的右子树，在走右子树时，同样是依照上面的规则去遍历，实际也就是利用了栈去模拟了递归的过程，这种好处就是可以不用频繁的建立函数栈帧，而是通过我们自己的栈去实现了这个过程
4.参考代码
（1）递归
class Solution {
public:
void recursion(TreeNode* root,int& k, int& ret)
{
if(root == nullptr)
return;
recursion(root->left,k,ret);
k--;
if(k == 0)
{
ret = root->val;
return;
}
recursion(root->right,k,ret);
}
int kthSmallest(TreeNode* root, int k)
{
int ret = 0;
recursion(root,k,ret);
return ret;
}
};（2）循环
class Solution {
public:
int kthSmallest(TreeNode* root, int k)
{
//题目中说到n是大于等于k的，所以可以不考虑找不到第k小的情况，或者节点为空的情况
stack<TreeNode*> s;
TreeNode* cur = root;
while(1)
{
while(cur)
{
s.push(cur);
cur = cur->left;
}
if(!s.empty())
{
TreeNode* date = s.top();
s.pop();
k--;
if(k == 0)
{
return date->val;
}
cur = date->right;
}
}
}
};代码分析
总结
本章总结了剑指offer的部分经典题目，也有稍微复杂的也有代码分析，这里的参考代码是用C++写的
