LeetCode | 0662. 二叉树最大宽度【Python】

痛定思痛。 2022-11-03 10:36 224阅读 0赞

问题

力扣

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:

  1. 输入: 
  2.        1
  3.      /   \
  4.     3     2
  5.    / \     \  
  6.   5   3     9 
  8. 输出: 4
  9. 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:

  1. 输入: 
  2.       1
  3.      /  
  4.     3    
  5.    / \       
  6.   5   3   
  8. 输出: 2
  9. 解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:

  1. 输入: 
  2.       1
  3.      / \
  4.     3   2 
  5.    /        
  6.   5      
  8. 输出: 2
  9. 解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4:

  1. 输入: 
  2.        1
  3.      / \
  4.     3   2
  5.    /     \  
  6.   5       9 
  7.  /         \
  8. 6           7
  10. 输出: 8
  11. 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

注意: 答案在32位有符号整数的表示范围内。

思路

BFS

  1. 满二叉树的特性：节点p的左子节点的序号为2p，右子节点的序号为2p+1。
  2. 同一层中，首末元素的坐标差就是最大宽度。

代码

Python3

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. # def __init__(self, val=0, left=None, right=None):
  4. # self.val = val
  5. # self.left = left
  6. # self.right = right
  7. class Solution:
  8.     def widthOfBinaryTree(self, root: TreeNode) -> int:
  9.         if not root:
  10.             return 0
  11.         # 分别是坐标和节点
  12.         queue = [(0, root)]
  13.         res = 1
  14.         # BFS
  15.         while queue:
  16.             # 首末元素的坐标差就是最大宽度
  17.             res = max(res, queue[-1][0] - queue[0][0] + 1)
  18.             tmp = []
  19.             for i, q in queue:
  20.                 if q.left:
  21.                     tmp.append((i * 2, q.left))
  22.                 if q.right:
  23.                     tmp.append((i * 2 + 1, q.right))
  24.             queue = tmp
  25.         return res

链接

GitHub

发表评论

表情：
评论列表 （有 0 条评论，224人围观）

还没有评论，来说两句吧...

相关阅读