給定一個(gè)二叉樹，編寫一個(gè)函數(shù)來獲取這個(gè)樹的最大寬度。樹的寬度是所有層中的最大寬度。這個(gè)二叉樹與滿二叉樹（full binary tree）結(jié)構(gòu)相同，但一些節(jié)點(diǎn)為空。每一層的寬度被定義為兩個(gè)端點(diǎn)（該層最左和最右的非空節(jié)點(diǎn)，兩端點(diǎn)間的null節(jié)點(diǎn)也計(jì)入長度）之間的長度。示例 1:輸入: 1/ \3 2/ \ \ 5 3 9 輸出: 4 解釋: 最大值出現(xiàn)在樹的第 3 層，寬度為 4 (5,3,null,9)。 示例 2:輸入: 1/ 3 / \ 5 3 輸出: 2 解釋: 最大值出現(xiàn)在樹的第 3 層，寬度為 2 (5,3)。 示例?3:輸入: 1/ \3 2 / 5 輸出: 2 解釋: 最大值出現(xiàn)在樹的第 2 層，寬度為 2 (3,2)。 示例 4:輸入: 1/ \3 2/ \ 5 9 / \6 7 輸出: 8 解釋: 最大值出現(xiàn)在樹的第 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

總結(jié)

以上是生活随笔為你收集整理的41. Leetcode 662. 二叉树最大宽度 (二叉树-二叉树性质)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。