二叉树的层序遍历就是Bfs(广度优先搜索)
因为步长一致
框架：
queue<TreeNode*>qu;qu.push(root);while(!qu.empty()){int siz=qu.size();//当前层结点数量for(int i=0;i<siz;++i){//当前层结点全部出队auto cur=qu.front();qu.pop();//下一层结点入队if(cur->left！=nullptr){qu.push(cur->left);}if(cur->right!=nullptr){qu.push(cur->right);}}}
应用
借助层序遍历，我们可以自然地知道每个结点在第几层
如果题目要求我们在水平方向上进行操作，那十有八九需要用到层序遍历的思想
只需：
queue<TreeNode*>qu;qu.push(root);int depth=0;//这里假设root深度为 1 ，若root深度为0这里初始化depth=-1即可while(!qu.empty()){depth++;//进入下一层int siz=qu.size();for(int i=0;i<siz;++i){auto cur=qu.front();qu.pop();if(cur->left！=nullptr){qu.push(cur->left);}if(cur->right!=nullptr){qu.push(cur->right);}}}
题目1
leetcode 117
给定一个二叉树：
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点
如果找不到下一个右侧节点，则将 next 指针设置为 NULL
初始状态下，所有 next 指针都被设置为 NULL
class Solution {
public:Node* connect(Node* root) {if(root==NULL)return NULL;queue<Node*>q;q.push(root);while(q.size()){int siz=q.size();Node*p=NULL;//对每一层设置一个前置结点for(int i=0;i<siz;++i){auto c=q.front();q.pop();if(p!=NULL)p->next=c;//跳过最左边的结点p=c;if(c->left)q.push(c->left);if(c->right)q.push(c->right);}}return root;}
};
题目2
leetcode 958
给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树
在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 h 层）中可以包含 1 到 2h 个节点
直接说思路：
允许nullptr结点入队，当弹出第一个nullptr时说明层遍历结束，此时队列中因该只剩下nullptr
如果后面还有非空结点，说明不是完全二叉树
class Solution {
public:bool isCompleteTree(TreeNode* root) {queue<TreeNode*>q;q.push(root);bool end=0;while(q.size()){int siz=q.size();for(int i=0;i<siz;++i){auto c=q.front();q.pop();if(c==nullptr)end=1;//弹出空结点else{if(end)return 0;//当前结点非空且之前弹出过空结点//这里我们运行nullptr结点入队q.push(c->left);q.push(c->right);}}}return 1;//处理到这里说明合法}
};
题目3
leetcode 919
思路
两个队列q,qu
q 中存储有空孩子的结点，即：->leftnullptr || ->rightnullptr
qu 用于初始化,找到有空孩子的结点
需要 insert 新结点时 : 弹出 q.front() ,让新节点成为它的孩子，孩子满了就出队
同时新插入的结点也没有孩子，进入 q
class CBTInserter {TreeNode*root;int de;queue<TreeNode*>q;
public:CBTInserter(TreeNode* root) {this->root=root;queue<TreeNode*>qu;qu.push(root);while(qu.size()){int siz=qu.size();for(int i=0;i<siz;++i){auto c=qu.front();qu.pop();if(c->left)qu.push(c->left);if(c->right)qu.push(c->right);if(c->left==nullptr||c->right==nullptr)q.push(c);}}}int insert(int val) {TreeNode*node=new TreeNode(val);auto c=q.front();int v=c->val;if(c->left==nullptr)c->left=node;else if(c->right==nullptr){c->right=node;q.pop();}q.push(node);return v;}TreeNode* get_root() {return root;}
};