目录
前提：
题目：
1.二叉树的层序遍历
思路：
代码：
2.二叉树的层序遍历
思路：
链接：
3.二叉树的层序遍历
思路：
代码：
4.填充每个节点的下一个右侧节点指针
思路：
5.填充每个节点的下一个右侧节点指针 II
思路：
6.二叉树的锯齿形层序遍历
题目：
思路：
7.N 叉树的层序遍历
思路：
前提：
首先我们要达成一个共识，进行二叉树的层序遍历的方法叫做广度优先搜索，是使用了队列这个数据结构来实现的
题目： 1.二叉树的层序遍历
给你一个二叉树，请你返回其按层序遍历得到的节点值 。（即逐层地，从左到右访问所有节点） 。
层序遍历结果为 3 9 20 15 7
思路：
我们先将根节点入队，
如果队列不为空，取队首元素，如果该元素左子树不为空，入队，如果该元素右子树不为空，入队；
直至队列位空，层序遍历完毕；
代码：

文章插图
vector levelOrder(TreeNode* root) {vector ret;if(root==nullptr)return ret;//根节点不为空，先将根节点入队TreeNode* curnode=root;queue que;que.push(curnode);TreeNode* end=root;while(!que.empty()){TreeNode* top=que.front();que.pop();//队首元素左子节点存在，入队if(top->left!=nullptr)que.push(top->left);//队首元素右子节点存在，入队if(top->right!=nullptr)que.push(top->right);ret.push_back(top->val);}//队列为空，层序遍历完毕return ret;}
2.二叉树的层序遍历
思路：
相较于1而言，只是将每层的数放在一个数组内，将整个树的结果存放在二位数组内，因此我们只要知道每一层的节点个数，就能够完成上面的层序遍历
（1.采用计数的方法，记录每一层的节点个数，如果全部遍历完毕，将一维数组的结果放入二位数组中
vector> levelOrder(TreeNode* root) {vector> result;if(root==nullptr){return result;}//nodeCount正在遍历的层的节点数int nodeCount=1;queue que;que.push(root);//curlevelCount下一层的节点个数int curlevelCount=0;vector arr;while(!que.empty()){TreeNode* tmp=que.front();que.pop();//每遍历一个节点，本层节点个数减1，本层节点个数为0的时候，本层节点全部遍历完毕；nodeCount--;arr.push_back(tmp->val);if(tmp->left!=nullptr){que.push(tmp->left);curlevelCount++;}if(tmp->right!=nullptr){que.push(tmp->right);curlevelCount++;}if(nodeCount==0){result.push_back(arr);arr.clear();nodeCount=curlevelCount;curlevelCount=0;}}return result; }
(2.记录每层最后一个节点，当我们正在遍历的节点是本层的最后一个节点，那么我们就可以将以为数组的结果，放入二位数组中
vector> levelOrder(TreeNode* root) {vector>ret;if(root==nullptr)return ret;queue que;que.push(root);//end本层的最后一个节点TreeNode* end=root;//nextend下一层的最后一个节点TreeNode* nextend=root;vector arr;while(!que.empty()){TreeNode* Node=que.front();arr.push_back(Node->val);que.pop();if(Node->left!=nullptr){que.push(Node->left);//防止出现子节点为空的情况nextend=Node->left;}if(Node->right!=nullptr){que.push(Node->right);//防止出现子节点为空的情况nextend=Node->right;}if(Node==end){end=nextend;ret.push_back(arr);arr.clear();}}return ret;}
优化：当我们取到最后一个节点的时候，下一层的最后一个节点就是队列当中的末尾元素
vector> levelOrder(TreeNode* root) {vector

• 上一页
• 1
• 2
• 3
• 下一页

• 24 day4 两两交换链表中的节点删除链表倒数第n个节点（19）环形链表（1
• JS获取元素的九种方法、节点，以及在JS中动态增删改元素
• Git总结和使用教程
• 每个学数据分析的人，都有这样的血泪史。
• 洪水填充算法详解
• C语言中关于如何删除链表的某个节点问题
• NC高频问题
• 提升“架构思维”？这本书值得一读
• 将一个数组变成二叉树
• 【Visio】图形交叠的不规则区域的提取和填充上色