662 二叉树最大宽度（宽搜搜索每一层的节点）

桃扇骨 2022-08-29 10:44 113阅读 0赞

**1. 问题描述：**

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

**示例 1:**

输入:  
1  
/ \\  
3 2  
/ \\ \\  
5 3 9

输出: 4  
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

**示例 2:**

输入:  
1  
/  
3  
/ \\  
5 3

输出: 2  
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

**示例 3:**

输入:  
1  
/ \\  
3 2  
/  
5

输出: 2  
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

**示例 4:**

输入:  
1  
/ \\  
3 2  
/ \\  
5 9  
/ \\  
6 7

输出: 8  
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。  
注意: 答案在32位有符号整数的表示范围内。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/maximum-width-of-binary-tree

**2. 思路分析：**

分析题目可以知道本质上求解的是每一层节点之间编号的最大差值，所以我们可以使用**宽搜**遍历每一层的节点即可，每一次遍历队列中当前这一层的所有节点，因为左孩子的编号为p \* 2，右孩子的编号为2 \* p + 1，其中p为父节点的编号，所以每一层的编号都是以2倍的速率来递增的，如果每一层的节点编号都是使用上一层节点的编号的2倍那么会导致编号太大了，这里我们可以采用每一层的节点从1开始编号，也即编号从当前这一层节点与最左边节点编号的差值开始的。

**3. 代码如下：**

import collections
    
    
    # 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: TreeNode) -> int:
            q = collections.deque([(root, 1)])
            res = 0
            while q:
                t = q[0]
                l, p = t[1], 1
                size = len(q)
                # 搜索当前这一层的所有节点
                for i in range(size):
                    t = q.popleft()
                    # 将当前的节点的编号从1开始, 其实求解的是两个节点编号的差值
                    node, p = t[0], t[1] - l + 1
                    if node.left: q.append((node.left, p * 2))
                    if node.right: q.append((node.right, p * 2 + 1))
                res = max(res, p)
            return res