11道精选经典LeetCode例题让你彻底搞懂二叉树的广度优先遍历
-
1.二叉树的层序遍历|
-
2.二叉树的层序遍历||
-
3.二叉树的右视图
-
4.二叉树的层平均值
-
5.n叉树的层数遍历
-
6.在每个树行找最大值
-
7.填充每个节点的下一个右侧节点指针
-
8.填充每个节点的下一个右侧节点指针||
-
9.二叉树的最大深度
-
10.二叉树的最小深度
-
11.翻转二叉树
相见即是有缘，如果对你有帮助，给博主一个免费的点赞以示鼓励把QAQ
广度优先搜索是遍历二叉树的一种基本方式，也就是层序遍历一个二叉树。从左到右一层一层的去遍历二叉树，对此我们需要借助数据结构队列来完成，因为队列先进先出的特点符合我们遍历的要求，也会成为我们解题的关键，今天我们用11道经典LeetCode算法题认识二叉树的广度优先搜索
有上述二叉树，我们利用队列Queue对其进行层序遍历
先使6提前进入队列
6进队列
第1轮遍历，6出队列，6的两个子节点 4,7进入队列
第2轮遍历，4出队列，4的1,3节点进队列，7出队列，7的5,8节点进队列
第3轮遍历 1,3，5,8为叶子结点，依次退出队列
下面我们结合11道题目对层序遍历进行理解
=========================================================================
public List<List> resList = new ArrayList<>();
public List<List> levelOrder(TreeNode root) {
// checkFun02(root,resList);
checkFun01(root,0);
return resList;
}
//BFS，广度优先遍历
private void checkFun02(TreeNode root, List<List> resList) {
if (root==null){
return;
}
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
int len = queue.size();
List list = new ArrayList<>();
while (len>0){
TreeNode poll = queue.poll();
list.add(poll.val);
if (poll.left!=null) queue.offer(poll.left);
if (poll.right!=null) queue.offer(poll.right);
len–;
}
resList.add(list);
}
}
//DFS 深度优先遍历
private void checkFun01(TreeNode root, int dep) {
if (root==null){
return;
}
dep++;
while (resList.size()<dep){
List list = new ArrayList<>();
resList.add(list);
}
resList.get(dep-1).add(root.val);
if (root.left!=null) checkFun01(root.left,dep);
if (root.right!=null) checkFun01(root.right,dep);
}
==========================================================================
public List<List> levelOrderBottom(TreeNode root) {
List<List> resList = new ArrayList<>();
if (root==null){
return resList;
}
Queue queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()){
int len = queue.size();
List list = new ArrayList<>();
while (len>0){
TreeNode poll = queue.poll();
list.add(poll.val);
if (poll.left!=null) queue.offer(poll.left);
if (poll.right!=null) queue.offer(poll.right);
len–;
}
resList.add(list);
}
Collections.reverse(resList);
return resList;
}
=======================================================================
注意右视图看到的元素指的不单单是右子树的元素，而是每一层最右侧的元素，这个元素也有可能出现在左子树，所以需要将每一层的最后一个元素加入集合
public List rightSideView(TreeNode root) {
List list = new ArrayList<>();
if (root==null){
return list;
}
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int len = queue.size();
while (len>0){
TreeNode poll = queue.poll();
if (len==1){
list.add(poll.val);
}
if (poll.left!=null) queue.offer(poll.left);
if (poll.right!=null) queue.offer(poll.right);
len–;
}
}
return list;
}
========================================================================
利用层序遍历，记录每一层的数字并计算平均值即可
public List averageOfLevels(TreeNode root) {
List list = new ArrayList<>();
if (root==null){
return list;
}
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
double sum = 0;
int len = queue.size();
int temp=len;
while (len>0){
TreeNode poll = queue.poll();
sum+=poll.val;
len–;
if (poll.left!=null) queue.offer(poll.left);
if (poll.right!=null) queue.offer(poll.right);
}
list.add(sum/temp);
}
return list;
}
========================================================================
public List<List> levelOrder(Node root) {
List<List> resList = new ArrayList<>();
if (root==null){
return resList;
}
Deque queue = new LinkedList<>();
queue.offerLast(root);
while (!queue.isEmpty()){
int len = queue.size();
List list = new ArrayList<>();
for (int i=0;i<len;i++){
Node poll = queue.pollFirst();
list.add(poll.val);
List children = poll.children;
if (children==null||children.size()==0){
continue;
}
for (Node child : children) {
if (child!=null){
queue.offerLast(child);
}
}
}
resList.add(list);
}
return resList;
}
=========================================================================
public List largestValues(TreeNode root) {
List list = new ArrayList<>();
if (root==null){
return list;
}
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int len = queue.size();
int max = Integer.MIN_VALUE;
for (int i=0;i<len;i++){
TreeNode poll = queue.poll();
if (poll.val>max){
max = poll.val;
}
if (poll.left!=null) queue.offer(poll.left);
if (poll.right!=null) queue.offer(poll.right);
}
list.add(max);
}
return list;
}
================================================================================
Queue queue = new LinkedList<>();
if (root==null){
return null;
}
queue.offer(root);
while (!queue.isEmpty()){
int len = queue.size();
Node nodePre = null;
Node node;
for (int i=0;i<len;i++){
if (i==0){
nodePre = queue.poll();
node = nodePre;
}else {
node = queue.poll();
nodePre.next = node;
nodePre = nodePre.next;
}
if (node.left!=null) queue.offer(node.left);
if (node.right!=null) queue.offer(node.right);
}
}
return root;
==================================================================================
这道题目说是二叉树，但第7题题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道
public Node connect2(Node root) {
Queue queue = new LinkedList<>();
if (root==null){
return null;
}
queue.offer(root);
自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。
深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！
因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！
由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！
如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）
最后
学习视频：
大厂面试真题：
《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！
64932)]
[外链图片转存中…(img-UgYMeKF5-1713035964933)]
[外链图片转存中…(img-P9HB8XFf-1713035964933)]
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！
由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！
如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）
最后
学习视频：
[外链图片转存中…(img-2YwSqvVb-1713035964933)]
大厂面试真题：
[外链图片转存中…(img-T38wqBhD-1713035964934)]
《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！
更多推荐
7
0- 0
已为社区贡献1条内容
所有评论(0)