怎么看别人网站是什么语言做的,谷歌浏览器网页版在线,广州外贸网站开发,注册公司流程和要求文章目录 前言二叉树最大宽度1.题目解析2.算法原理3.代码编写 总结 前言
二叉树最大宽度
1.题目解析
给你一棵二叉树的根节点 root #xff0c;返回树的 最大宽度 。 树的 最大宽度 是所有层中最大的 宽度 。 每一层的 宽度 被定义为该层最左和最右的非空节点#xff08;即… 文章目录 前言二叉树最大宽度1.题目解析2.算法原理3.代码编写 总结 前言
二叉树最大宽度
1.题目解析
给你一棵二叉树的根节点 root 返回树的 最大宽度 。 树的 最大宽度 是所有层中最大的 宽度 。 每一层的 宽度 被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的 null 节点这些 null 节点也计入长度。 题目数据保证答案将会在 32 位 带符号整数范围内。 输入root [1,3,2,5,3,null,9] 输出4 解释最大宽度出现在树的第 3 层宽度为 4 (5,3,null,9) 。 输入root [1,3,2,5,null,null,9,6,null,7] 输出7 解释最大宽度出现在树的第 4 层宽度为 7 (6,null,null,null,null,null,7) 。
2.算法原理 思路一 统计每一层的最大宽度优先想到的就是层序遍历把当前层节点全部存在队列中利用队列的长度计算每一层的宽度就可以统计出最大宽度。
空节点也是现需要计算的将空节点也存放在队列中。 但是在极端场景下最左边一条长链最右边一条长链我们就需要几亿个节点超出内存限制。 这个思路是错误的 思路二: 依旧是利⽤层序遍历但是这⼀次队列⾥⾯不单单存结点信息并且还存储当前结点如果在数组中存储所对应的下标在我们学习数据结构 - 堆的时候计算左右孩⼦的⽅式这样我们计算每⼀层宽度的时候⽆需考虑空节点只需将当层结点的左右结点的下标相减再加 1 即可。
但是这⾥有个细节问题如果⼆叉树的层数⾮常恐怖的话我们任何⼀种数据类型都不能存下下标 的值。但是没有问题因为 • 我们数据的存储是⼀个环形的结构 • 并且题⽬说明数据的范围在 int 这个类型的最⼤值的范围之内因此不会超出⼀圈 • 因此如果是求差值的话我们⽆需考虑溢出的情况。
3.代码编写
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {queuepairTreeNode*,unsigned intq;if(rootnullptr){return 0;}q.push({root,1});unsigned int maxlen1;while(!q.empty()){int nq.size();unsigned int beginq.front().second;unsigned int endq.back().second;maxlenmax(maxlen,end-begin1);for(int i0;in;i){TreeNode*tq.front().first;if(t-left){q.push({t-left,q.front().second*2});}if(t-right){q.push({t-right,q.front().second*21});}q.pop();}}return maxlen;}
};总结
以上就是今天要讲的内容。希望对大家的学习有所帮助仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~
