【剑斩OFFER】算法的暴力美学——leetCode 662 题：二叉树最大宽度

一、题目描述

二、算法原理

思路：使用队列实现层序遍历 + 让节点绑定一个下标 pair< TreeNode* , unsigned int>

例如：

计算左节点的下标的公式：父亲节点 * 2

计算右节点的下边的公式：父亲节点 * 2 + 1

第一层的宽度：1

第二层的宽度：3 - 2 + 1 = 2

第三层的宽度：6 - 4 + 1 = 3

故而最大的宽度位3

为什么使用 unsigned int 因为数值溢出了也不报错。

当使用 int 时，即使一个数溢出了：

此时这两个数其中一个溢出了，但是相减出来的值是正确的，不过这样编译器会报错，所以使用 unsigned int

三、代码实现

/** * 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) { if(root == nullptr) return 0; queue<pair<TreeNode*,unsigned int>> que;//给每个节点绑定一个下标 que.push({root,1});//让 root 绑定 1 下标 unsigned int maxi = 0;//记录最大的宽度 while(!que.empty()) { int popnum = que.size(); unsigned int l = que.front().second;//左边的节点的下标 unsigned int r = 0; while(popnum--) { pair<TreeNode*,unsigned int> node = que.front(); que.pop(); unsigned int index = node.second; if(node.first->left != nullptr) { que.push({node.first->left,2 * index}); } if(node.first->right != nullptr) { que.push({node.first->right,2 * index + 1}); } if(popnum == 0) r = index;//最右节点的下标 } maxi = max(maxi, r - l + 1); } return maxi; } };