广度优先搜索 （Breadth First Search），又叫层次遍历或宽度优先搜索，通常是以二叉树或图作为研究对象，先从上往下对该二叉树的每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完当前层才进入下一层，直到没有结点可以访问为止。
【leetcode-102】给你二叉树的根节点 ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
3.1.1 大致思路
创建两个vector，分别为cur和next，其中cur含有当前访问层中的所包含的节点，next含有cur（极next的上一层）的各个节点的左右子节点，创建一个数组vals用来储存各个节点的值。遍历cur中的每个节点，将其每个节点的子节点放入next中，如果是nullptr就不放（这样的话，直到该二叉树的最后一层，将不再有子节点，也可以成为循环的符合条件），同时，将cur中的每个节点的节点值放到vals中，遍历结束后将cur替换成next就可以才是下一轮的遍历了，知道cur中不再有节点为止。
3.1.2 具体步骤
1 声明一个cur的数组，并使其初始化含有root节点；
2 以cur数组中存在节点为条件，开始外层循环；
3 声明一个数组vals用来储存cur数组个各个节点的值；
4 声明一个数组next以从左到右（或从右到左）的顺序，来储存cur的子节点；
5 开始内层循环用来将cur数组中的节点的值放入vals中，并且将cur中的各个子节点的存放到next中；
6 离开内层循环（仍在外层循环内），开始善后工作:将vals放入ans内,将cur数组用next来替换
3.1.3 代码
讯享网
3.2.1 大致思路
利用队列这个数据结构（先进先出）的特性，将root节点放入队列中去，然后将其值赋个用来储存各个节点值的vals数组中，然后将该节点的各个子节点再放入相同的队列（即自己这个节点的后面），如此循环。
3.2.2 具体步骤
1 声明答案ans，一个存放节点的队列q，并将root节点放到q中去；
2 以队列q不是空的作为循环条件，开启外层循环用来依次存放当前层的节点；
3 声明一个用来储存各节点值的数组vals；
4 以队列中仍有节点为循环条件，开启内层循环用来遍历当前层的节点；
5 内层循环中，声明一个暂时的变量用来存放队列头部的节点；
6 存放完成后弹出头节点，并将头节点的值存放入vals中；
7 检查当前节点是否有子节点，如有，将其子节点放入队列
8 跳出内层循环（仍在外层循环中），将vals存放入ans中
3.2.3 代码
讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/203123.html