层序遍历
算法流程:
1.创建一个队列记为que,将根节点放入队列。
2.每次从队列中弹出一个节点,记为node。
3.第三步看这个node有没有左孩子,如果有左孩子把左孩子放入到队列中,如果node有右孩子,把右孩子放入到队列中。
4.重复步骤二和步骤三,直到队列为空。
相关函数和知识:
#include"Tree.h"
int main()
{
vector<int>vec;
//二维数组就是一维数组中的元素是一维数组
vector<vector<int>>vec1;
vec1.push_back(vec);
//排序函数
sort(vec.begin(), vec.end());//从小到大排序
sort(vec.rbegin(), vec.rend());//从大到小排序
reverse(vec.begin(), vec.end());//反转数组
}
二叉树的层序遍历
102. 二叉树的层序遍历https://leetcode.cn/problems/binary-tree-level-order-traversal/
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
思路
通过维护一个队列实现了对二叉树的层序遍历。首先,根节点入队。然后,当队列不为空时,循环执行:遍历当前队列中的所有节点,将它们的值收集到一个二维向量中,并将它们的非空左右子节点依次入队。每完成一层的遍历,就将这一层的向量添加到结果向量中,直到遍历完所有层。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(root==nullptr) return {};
queue<TreeNode*>que;
que.push(root);
vector<vector<int>>res;
while(!que.empty())
{
vector<int>vec;
int n=que.size();
for(int i=0;i<n;i++)
{ TreeNode*front=que.front();
que.pop();
vec.push_back(front->val);
if(front->left)
que.push(front->left);
if(front->right)
que.push(front->right);
}
res.push_back(vec);
}
return res;
}
};
二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
给你二叉树的根节点 root
,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
思路
这段代码实现了二叉树的锯齿形层序遍历。它使用了队列来进行层序遍历,同时通过一个布尔变量
flag
来标记是否需要反转当前层的节点值顺序。每次遍历一层时,先将该层的节点值存入一个临时的 vector 中,然后根据flag
变量的值决定是否需要反转该 vector,最后将其加入结果 vector 中。这样可以实现从左向右和从右向左交替进行层序遍历。
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(root==nullptr) return {};
vector<vector<int>>res;
queue<TreeNode*>que;
que.push(root);
bool flag=false;
while(!que.empty())
{
vector<int>vec;//写在循环里会每次都清空
int n=que.size();
for(int i=0;i<n;i++)
{
TreeNode*front=que.front();
que.pop();
vec.push_back(front->val);
if(front->left) que.push(front->left);
if(front->right) que.push(front->right);
}
if (flag)
reverse(vec.begin(), vec.end());
flag=!flag;
res.push_back(vec);
}
return res;
}
};
先序遍历
Preorder算法流程:
1.先申请一个栈,记为stk。
2.然后将根节点压入stk 中。
3.每次从stk 中弹出栈顶节点,记为cur,然后打印cur的值。如果cur的右子节点不为空,将cur的右子树压入stk 中。如果cur的左子树不为空,将cur的左子节点压入stk 中。不断重复次步骤3直到stk为空循环结束。
二叉树展开为链表
114. 二叉树展开为链表https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
提示
给你二叉树的根结点 root
,请你将它展开为一个单链表:
- 展开后的单链表应该同样使用
TreeNode
,其中right
子指针指向链表中下一个结点,而左子指针始终为null
。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
思路
通过先序遍历二叉树的方式,将每个节点按顺序连接到单链表中。利用栈来模拟递归的过程,先将根节点入栈,然后不断弹出栈顶节点,将其右子节点和左子节点依次入栈,同时将当前节点连接到链表中。
class Solution {
public:
void flatten(TreeNode* root) {
if(root==nullptr) return ;
stack<TreeNode*>stk;
stk.push(root);
TreeNode *H=new TreeNode(),*T=H;//因为头节点不知道拼在哪 故创建一个虚头节点
while (!stk.empty())
{
TreeNode* top = stk.top();
stk.pop();
T->right=top;
T->left=nullptr;
T=T->right;
if (top->right) stk.push(top->right);//因为栈是后进先出 所以右子树先进
if (top->left) stk.push(top->left);
}
delete H;
}
};