---

題目鏈接：

662. 二叉樹最大寬度

---

題目描述：

---

解法

這里的寬度指的是一層的最右邊的非空節點到一層的最左邊的非空節點，一共的節點數。

解法一：硬來（會超時，因為可能會有3000個數的左右各1500個節點的最惡心的情況）

仿照之前的層序遍歷，把空節點也加進去。（要注意，遇到空節點要添加兩個空孩子）

解法二：利用數組存儲二叉樹的方式，給節點編號。

寬度就是這個隊列的隊尾和隊頭相減再加一。

也可以直接搞一個數組來模擬。

注意細節：下標有可能會溢出。

不過當我們相減之后，即使溢出，結果也是正確的。因為存儲實際上是一個環，所以我們可以使用無符號整數來存儲。

---

C++ 算法代碼：

/*** 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) {// 計算二叉樹最大寬度算法// 基本思路：使用層序遍歷，同時為每個節點分配位置編號// 寬度定義為：每一層最右邊節點與最左邊節點的位置差+1// 使用數組模擬隊列，存儲節點和其位置編號// 使用unsigned int避免大數時可能的整數溢出vector<pair<TreeNode*, unsigned int>> q;q.push_back({root, 1});  // 根節點入隊，位置編號為1unsigned int ret = 0;    // 存儲最大寬度結果while(q.size())  // 只要隊列不為空，就繼續處理{// 計算當前層的寬度：最右節點位置減去最左節點位置再加1auto& [x1, y1] = q[0];       // 當前層最左邊的節點x1及其位置y1auto& [x2, y2] = q.back();   // 當前層最右邊的節點x2及其位置y2ret = max(ret, y2 - y1 + 1); // 更新最大寬度// 準備處理下一層節點vector<pair<TreeNode*, unsigned int>> tmp; // 臨時數組，存儲下一層的節點// 遍歷當前層的所有節點，將其子節點加入到下一層for(auto& [x, y] : q){// 關鍵：為子節點分配位置編號// 左子節點的位置是父節點位置的2倍if(x->left) tmp.push_back({x->left, y * 2});// 右子節點的位置是父節點位置的2倍加1if(x->right) tmp.push_back({x->right, y * 2 + 1});}q = tmp;  // 更新隊列，準備處理下一層}return ret;  // 返回最大寬度}
};