本文主要是介绍LeetCode 662. 二叉树最大宽度（层序遍历，防溢出），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
思路：
一开始用深度优先遍历计数来写的，但是这样会溢出。通过层序遍历，每次优先遍历完这一层，并且计数值减去起点计数值，就不会溢出了。
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {if(!root) return 0;queue<pair<TreeNode*, int>>q;q.push({root, 0});int ans = 0;while(!q.empty()) {pair<TreeNode*, int>first = q.front();int start = first.second;int cnt = q.size(); //保证遍历完这一层while(cnt--) {pair<TreeNode*, int>now = q.front();q.pop();if(now.first -> left) q.push({now.first -> left, now.second * 2 - start * 2});if(now.first -> right) q.push({now.first -> right, now.second * 2 + 1 - start * 2});ans = max(ans, now.second - start + 1);}}return ans;}
};
这篇关于LeetCode 662. 二叉树最大宽度（层序遍历，防溢出）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
