【栈与队列】二叉树最大宽度

662. 二叉树最大宽度

662. 二叉树最大宽度

​ 给你一棵二叉树的根节点 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

解题思路：队列 + 广度搜索

​ 一开始上来写这道题的时候，我想到的是广度搜索，然后既然题目要求的是空节点也算入内，那么我就想着每次插入队列的时候，把空节点也入队列，然后每次在广度搜索每一层的时候，就使用变量遍历寻找最左边的非空节点和最右边的非空节点，最后得到整个区间的长度！ ​ 但是很明显这种生硬的做法在这道题是不行的，因为如果这棵树是从根节点开始，左子树一直延伸下去，右子树一直延伸下去，这个高度就达到了接近 1500 层，那么节点的个数算上空节点个数的话，将近 2^1500 个节点，不说最后一层要遍历多久，单纯这个空间占用就十分的高了，所以这种方法是想不通的！ ​ 换个思路想，其实上面这种方法是可以的，但是问题是我们还将没必要的空节点计入了队列中，这就导致了时间复杂度和空间复杂度的大幅度上涨！所以我们要想办法既不需要将空节点算入队列中，还可以知道每一层有多少个空节点！ ​ 很显然上面的想法可行，但是不好做，所以我们再换个思路，既然不知道每层有多少个空节点，那么我们只需要找出最左节点的位置，以及最右节点的位置，然后用最右节点的位置减去最左节点的位置得到的就是该层的宽度！ ​ 所以我们现在需要想办法找出最左节点和最右节点的位置，这里就可以 借鉴用数组以及数组下标方式存放树节点的方式 了！ ​ 因为学二叉树的时候我们讲过，不只是可以用链表的方式存储，还可以使用数组方式存储，然后 通过其下标快速找到对应的左右孩子节点，最经典的例子就是我们学过的堆结构了！

​

​ 所以我们可以使用队列来进行广度搜索，然后队列中存放的元素不再是一个 TreeNode* 了，而是 存放一个键值对 pair<TreeNode*, int>，其中键就是对应的节点，然后值就是该节点在数组中对应其父节点的下标！

​ 然后我们将一层节点入队列之后，在下一次处理这一层节点的时候，我们可以直接通过队列的 front() 以及 back() 接口就得到该层最左和最右的两个节点的键值对，然后获取最左节点的下标，以及最右节点的下标，然后让 【最右节点的下标 - 最左节点的下标 + 1】 就得到了当前这一层的宽度！

​ 而此时数组下标从根节点开始，有两种记法：

• 第一种是以 0 下标开始，则此时左孩子节点就是 2*x + 1，右孩子节点就是 2*x + 2。
• 第二种是以 1 下标开始，则此时左孩子节点就是 2*x，右孩子节点就是 2*x + 1。

​ 这里我们采用第二种方式作为根节点起始下标，如下图所示：

​ 此时还有一个细节问题，就是这道题的溢出问题，很多题解没有讲清楚，为什么右孩子节点下标溢出了，结果还是对的，并且为什么 c++ 选手要用 unsigned int 存储下标，这里我们来解释一下！

​ 我们仔细一想，前面说过如果这棵树是从根节点开始，左子树一直延伸下去，右子树一直延伸下去，这个高度就达到了接近 1500 层，那么节点的个数算上空节点个数的话，将近 2^1500 个节点，此时对于右孩子节点的下标来说是溢出的，但其实我们让右孩子节点的下标减去左孩子节点的下标之后，是一个满足 int 类型范围的结果，这是题目保证的！

​ 之所以右孩子节点的下标溢出之后，减去左孩子节点的下标还能得到正确结果，其实就是因为我们之前学过的有符号整型它的取值范围问题，其实是呈现一个环状的，我们只要保证这个右孩子节点的下标溢出之后不要绕着这个取值范围的环状超过一圈即可，因为如果超过了一圈的话，那么直接用右孩子节点的下标减去左孩子节点的下标的话，会漏了超出的圈数的值，不过好在题目保证的答案将会在 32 位带符号整数范围内，就保证了右孩子节点的下标溢出之后，是不会说超过 32 位带符号整数范围的环状结构一圈的，这样子我们让右孩子节点的下标减去左孩子节点的下标之后得到的就还是一个正确的答案！

​ 至于为什么 c++ 选手要使用无符号整数 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) {
        // key表示节点，value表示在数组中的下标（通过下标的减法我们可以快速得到区间的长度）
        // 并且要使用unsigned int来存储下标，防止溢出
        // 这里默认根节点从1开始，那么左孩子就是2x，右孩子就是2x+1
        queue<pair<TreeNode*, unsigned int>> qe; 
        qe.push(make_pair(root, 1)); 

        unsigned int maxlen = 1;
        while(!qe.empty())
        {
            // 先直接利用队列获取首尾节点计算出区间长度
            maxlen = max(maxlen, qe.back().second - qe.front().second + 1); 

            // 然后让下一层入队列
            int n = qe.size();
            for(int i = 0; i < n; ++i)
            {
                pair<TreeNode*, unsigned int> front = qe.front();
                qe.pop();
                
                if(front.first->left != nullptr)
                    qe.push(make_pair(front.first->left, 2*front.second));
                if(front.first->right != nullptr)
                    qe.push(make_pair(front.first->right, 2*front.second + 1));
            }
        }
        return maxlen;
    }
};