LeetCode: 662. 二叉树最大宽度¶
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位有符号整数的表示范围内。
2、解题思路¶
- 层次遍历
- 在层次遍历的同时,保存节点的索引号
1 2 3 4 5 6 7
如上,左子节点的索引号为当前节点索引号的2*index
,右子节点为2*index+1
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def widthOfBinaryTree(self, root: TreeNode) -> int: if not root: return 0 res = 1 temp = [(root, 1)] while temp: _, left = temp[0] _, right = temp[-1] res = max(res, right - left + 1) t = [] for node, index in temp: if node.left: t.append((node.left, 2 * index)) if node.right: t.append((node.right, 2 * index + 1)) temp = t return res