662. 二叉树最大宽度 - 力扣LeetCode662. 二叉树最大宽度 - 给你一棵二叉树的根节点 root 返回树的 最大宽度 。树的 最大宽度 是所有层中最大的 宽度 。每一层的 宽度 被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的 null 节点这些 null 节点也计入长度。题目数据保证答案将会在 32 位 带符号整数范围内。 示例 1[https://assets.leetcode.com/uploads/2021/05/03/width1-tree.jpg]输入root [1,3,2,5,3,null,9]输出4解释最大宽度出现在树的第 3 层宽度为 4 (5,3,null,9) 。示例 2[https://assets.leetcode.com/uploads/2022/03/14/maximum-width-of-binary-tree-v3.jpg]输入root [1,3,2,5,null,null,9,6,null,7]输出7解释最大宽度出现在树的第 4 层宽度为 7 (6,null,null,null,null,null,7) 。示例 3[https://assets.leetcode.com/uploads/2021/05/03/width3-tree.jpg]输入root [1,3,2,5]输出2解释最大宽度出现在树的第 2 层宽度为 2 (3,2) 。 提示 * 树中节点的数目范围是 [1, 3000] * -100 Node.val 100https://leetcode.cn/problems/maximum-width-of-binary-tree/一、题目题意给定一棵二叉树计算二叉树的最大宽度。 每一层的宽度被定义为该层最左侧节点与最右侧节点之间的节点数量包含中间的空节点。第一层宽度1 第二层宽度2 第三层宽度45、null、3、null、9左右间距 4 最大宽度为 4。代码核心逻辑拆解初始化队列根节点编号初始为 1存入队列层序循环每次处理完整一层计算层宽度每层第一个元素是最左节点末尾元素是最右节点差值 1 为本层宽度生成下一层按堆编号规则给左右子树分配编号队列更新用临时容器存储下一层替换原队列完成分层 BFS。/** * 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) { vectorpairTreeNode*,unsigned long long q; q.push_back({root ,1}); unsigned long long ret0; while(q.size()) { auto [x1,y1]q[0]; auto [x2,y2]q.back(); retmax(ret,y2-y11); vectorpairTreeNode*,unsigned long long 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*21}); } qtmp; } return ret; } };