当前位置: 首页 > news >正文

队列+宽搜(BFS)-662.二叉树最大宽度-力扣(LeetCode) - 指南

目录

一、题目解析

1、宽度定义为最左节点和最右的非空节点之间的长度

2、类比char的存储(一个首尾相连的环,127+1!=128 = -127),哪怕int可能会溢出,但是所得的差,由题目保证的32位范围内,所以结果是不会溢出的

二、算法原理

解法1:直接统计nullptr的数目(这虽然是一个错误的解法,但仍有其价值)

解法2:利用数组存储二叉树,给节点编号

编号呢有两种,行自行选择

宽度的保存

具体过程

三、代码示例

解法2:

看到最后,如果对您有所帮助,还请点赞、收藏和关注一键三连,在未来还会继续带来优秀的内容,感谢观看,大家下期再见!


一、题目解析

1、宽度定义为最左节点和最右的非空节点之间的长度

2、类比char的存储(一个首尾相连的环,127+1!=128 = -128),虽然int可能会溢出,但所得的差,由题目保证的32位范围内,因此结果是不会溢出的

二、算法原理

一个错误的解法,但仍有其价值)就是解法1:直接统计nullptr的数目(这纵然

在遇到第一个非空节点后,开始统计nullptr的数目,在遇到下一个非空节点时,返回结果

错误之处:

存在着某个测试样式,将3000个节点左右均分,所以此时最后一层的节点树大概有2^1497个这么多

但我们在学习二叉树的时候,简单模拟是通过数组实现的,可能通过给节点编号,将节点存储在数组中,故而便有了解法2

解法2:利用数组存储二叉树,给节点编号

之前的队列都是只存储节点的指针,但我们要利用编号进行宽度计算,所以queue中或者vector模拟应存储一个pair<TreeNode*,long>的类型的数据,为什么用long呢?当然是int编号溢出了

编号呢有两种,可以自行选择

如此就是1、root为0,左孩子为2*0+1,右孩子为2*0+2,其他节点也

2、root为1,左孩子为2*1,右孩子为2*1+1,其他节点也是如此

宽度的保存

结合题目和 char存储的模型,我们知道了最后的结果是有效的,但该如何保存该宽度呢?依据unsigned int无符号整数存储这个宽度,但是为了方便得到最终的最大值,可以初始化为1(也允许处理只有根的情况)

具体过程

参考层序遍历,只不过中间有一些空节点需要处理

在对每一层遍历时,先统计队列中的元素个数,这个个数代表该层元素个数,也代表循环次数

我们first是TreeNode*,用于判断它的左右孩子是否入队(我这里选择是nullptr不入队),second是节点的编号,用于计算宽度

在层序遍历完后,取出队列对头(左端点)和队尾(右端点),计算宽度并且与上一次结果比较,如果比上次大则更新宽度,否则不更新

三、代码示例

解法2:

class Solution {
public:
int widthOfBinaryTree(TreeNode* root)
{
queue> qti;
unsigned int ret = 1;//特殊处理只有根
if(root) qti.push({root,0});//入根
while(qti.size())
{
int num = qti.size();
pair tmp;//int会溢出
while(num--)//执行每层个数次
{
tmp = qti.front();
qti.pop();
if(tmp.first->left) qti.push({tmp.first->left,2*(tmp.second)+1});//不入空
if(tmp.first->right) qti.push({tmp.first->right,2*(tmp.second)+2});//通过编号计算宽度
}
if(qti.size())
ret = ret>qti.back().second-qti.front().second+1 ? ret : qti.back().second-qti.front().second+1;//取对头和队尾做计算
}
return ret;
}
};

看到最后,如果对您有所帮助,还请点赞、收藏和关注一键三连,在未来还会继续带来优秀的内容,感谢观看,我们下期再见!

http://www.hskmm.com/?act=detail&tid=18654

相关文章:

  • JWT攻防实战:混淆、破解与红队利用技术详解
  • “中国英伟达”投资人,赚翻了
  • The 3rd UCUP Stage 29: Metropolis(QOJ contest 1913) 总结
  • 空白金兰契的多维解构与实践路径:从价值表征困境到人机共生伦理
  • 2025中国制造企业500强榜单发布
  • 读 WPF 源代码 了解获取 GlyphTypeface 的 CharacterToGlyphMap 的数量耗时原因
  • 张江,首个万亿市值巨头诞生!
  • Java 与智慧交通:车联网与自动驾驶支持
  • 9月26号
  • 初衷的澄明:空白金兰契的深意
  • Aidoku - 专为iOS/iPadOS打造的免费开源漫画阅读器
  • windos的hyper-v安装的宝塔面板,在面板里面点击重启服务器后再也无法启动面板。
  • Obsidia Git同步方法(偏安卓)
  • 什么是 FullGC
  • Unity渲染时的排序规则
  • AI智慧的三重跃升:从「数理魔兽」到「悬荡悟空」的文明协作者
  • 新学期每日总结(第 5天)
  • codeforces round 1054(e.f)
  • 【SimpleFOC-小项目】驱动电机正转3周
  • 联合体union的基本用法
  • 弱结构光三维扫描重建
  • 9.27 git与pycharm
  • PCA降维
  • docker复制文件到宿主机
  • 【SimpleFOC】SimpleFOC的运动规划器(Motion Planner)和梯形速度规划
  • Day22多态详解
  • rad/s RPM之间的换算
  • 再见Playwright!谷歌官方Chrome DevTools MCP正式发布,AI编程效率再翻倍
  • Markdown 之——清单の语法
  • “计算理论之美”课程笔记一:概率