41. Leetcode 662. 二叉树最大宽度 (二叉树-二叉树性质)

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（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)。# 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:if root == None:return 0queue = [(root, 1)]width = 0while queue:length = len(queue)for i in range(length):node, num = queue.pop(0)if i == 0:first_num = numif i == length - 1:last_num = numwidth = max(width, last_num - first_num + 1)if node.left != None:queue.append((node.left, 2 * num))if node.right != None:queue.append((node.right, 2* num + 1))return width

总结

以上是生活随笔为你收集整理的41. Leetcode 662. 二叉树最大宽度 (二叉树-二叉树性质)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。