二叉树最大宽度

难度: Medium

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

Submission

运行时间: 28 ms

内存: 17.4 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
   
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 1
        arr = [[root, 1]]
        while arr:
            tmp = []
            for node, index in arr:
                if node.left:
                    tmp.append([node.left, index * 2])
                if node.right:
                    tmp.append([node.right, index * 2 + 1])
            res = max(res, arr[-1][1] - arr[0][1] + 1)
            arr = tmp
        return res

Explain

这个题解使用了BFS的思路来解决二叉树最大宽度的问题。通过给每个节点标记唯一的索引值，可以计算出每一层的宽度。索引值的计算方式是：左子节点的索引值为父节点索引值的2倍，右子节点的索引值为父节点索引值的2倍加1。在BFS遍历的过程中，记录每一层最左边和最右边节点的索引值之差再加1，就可以得到该层的宽度。最后返回所有层宽度的最大值即可。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
   
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 1
        arr = [[root, 1]]  # 初始化队列，存储节点和对应的索引值
        while arr:
            tmp = []
            for node, index in arr:
                if node.left:
                    tmp.append([node.left, index * 2])  # 左子节点的索引值为父节点索引值的2倍
                if node.right:
                    tmp.append([node.right, index * 2 + 1])  # 右子节点的索引值为父节点索引值的2倍加1
            res = max(res, arr[-1][1] - arr[0][1] + 1)  # 更新最大宽度
            arr = tmp  # 更新队列
        return res

Explore

在BFS遍历的实现中，通常不会将null节点加入到队列中，因此不存在一层全部是null节点的情况。如果某一层的所有节点都没有子节点，那么这些null子节点不会被添加到队列中，所以下一层的队列会是空的，遍历也随之结束。因此，这种情况不会影响宽度的计算，因为计算宽度只考虑非null的节点。

BFS自然地按层级遍历二叉树，每次处理一层的所有节点，这使得计算每层的宽度变得直接和简单。使用BFS时，我们可以轻松地在每一层的遍历开始和结束时获取最左和最右节点的索引，这样就可以计算出层的宽度。而DFS以深度优先的方式遍历树，节点的处理顺序是从上到下然后是从左到右，这使得在不同的递归调用中保持层宽度信息变得复杂和不直观。因此，BFS在处理层级宽度的情况下更为合适且易于实现。

是的，在非常深的二叉树中，节点的索引值可能会非常大，尤其是在二叉树的层数达到较高值时。由于索引是按照二进制位的方式计算（每深入一层，索引大约翻倍），这可能导致整数溢出，特别是在使用有符号整数类型时。为防止这种情况，可以使用Python的长整型（自动处理大数），或者在其他语言中使用更大范围的整数类型，例如Java中的BigInteger。

是的，这种计算方式考虑了所有边界情况。这个表达式计算的是当前层最右边节点的索引与最左边节点的索引之差再加1。即使层中只有一个节点，这个计算仍然有效，因为最左和最右的索引相同，所以`arr[-1][1] - arr[0][1] + 1`结果为1，正确地反映了这层只有一个节点的宽度。