个人主页：C++忠实粉丝
欢迎 点赞???? 收藏✨ 留言✉ 加关注????本文由 C++忠实粉丝 原创队列 + 宽搜算法(3)_二叉树最大宽度
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论????
目录
1. 题目链接
2. 题目描述
3. 解法
算法思路:
代战展示:
1. 题目链接
OJ链接 ;二叉树最大宽度 https://leetcode.cn/problems/maximum-width-of-binary-tree/
2. 题目描述
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1：
输入：root = [1,3,2,5,3,null,9] 输出：4 解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：
输入：root = [1,3,2,5,null,null,9,6,null,7] 输出：7 解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：
输入：root = [1,3,2,5] 输出：2 解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
提示：
- 树中节点的数目范围是
[1, 3000] -100 <= Node.val <= 100
3. 解法
算法思路:
利用二叉树的顺序存储 - 通过跟节点的下标, 计算左右孩子的下标:
依旧是利用层序遍历, 但是这一次队列里面不单单存节点信息, 并且还存贮当前节点如果在数组中存储对应的下标(比如我们的堆就是利用数组下标计算左右孩子)
这样我们计算每一层宽度的时候, 无需考虑空节点, 只需将层节点的左右节点的下标相减再加1即可.
但是, 这里有一个细节问题 : 如果二叉树的层数非常恐怖的话, 我们任何一种数据类型都不能存下下标的值, 但是没有问题, 因为
1. 我们数据的存储是一个环形结构:
2. 并且题目说明, 数据的范围在int这个类型的最大值范围之内, 因此不会超出一圈;
3. 因此, 如果是求差值的话, 我们无需考虑溢出的情况.
代战展示:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode* root)
{
vector<pair<TreeNode* , unsigned int>> q;
if(root == nullptr) return 0;
q.push_back({root, 1});
unsigned int ret = 0;
while(q.size())
{
int sz = q.size();
auto [x1, y1] = q[0];
auto [x2, y2] = q.back();
ret = max(ret, y2 - y1 + 1);
vector<pair<TreeNode*, unsigned int>> tmp;
for(auto [x, y] : q)
{
if(x->left) tmp.push_back({x->left, y * 2});
if(x->right) tmp.push_back({x->right, y * 2 + 1});
}
q = tmp;
}
return ret;
}
};