LeetCode | 0662. 二叉树最大宽度【Python】
LeetCode | 0662. 二叉树最大宽度【Python】
问题
力扣
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（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位有符号整数的表示范围内。
思路
BFS
满二叉树的特性：节点p的左子节点的序号为2p，右子节点的序号为2p+1。
同一层中，首末元素的坐标差就是最大宽度。
代码
Python3
# 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: TreeNode) - int:
if not root:
return 0
# 分别是坐标和节点
queue = [(0, root)]
res = 1
# BFS
while queue:
# 首末元素的坐标差就是最大宽度
res = max(res, queue[-1][0] - queue[0][0] + 1)
tmp = []
for i, q in queue:
if q.left:
tmp.append((i * 2, q.left))
if q.right:
tmp.append((i * 2 + 1, q.right))
queue = tmp
return res
链接
GitHub
LeetCode | 0662. 二叉树最大宽度【Python】 相关文章
- LeetCode | 0655. 输出二叉树【Python】
问题 力扣 在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则： 行数 m 应当等于给定二叉树的高度。 列数 n 应当总是奇数。 根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和
- 【栈和队列】leetcode150——逆波兰表达式求值
编号150： 逆波兰表达式求值 根据 逆波兰表示法 ，求表达式的值。 有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 说明： 整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值
- Leecode - 实现乘方
leetcode（java实现） 问题描述： 50.pow(x,y) Implementpow(x,n), which calculatesxraised to the powern(x^n). Example 1: Input: 2.00000, 10Output: 1024.00000 Example 2:Input: 2.10000, 3 Output: 9.26100 Example 3:Input: 2.00000, -2 Output: 0.2
- [Leetcode]6. Z 字形变换
题目描述 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行Z 字形排列。 比如输入字符串为 "PAYPALISHIRING"行数为 3 时，排列如下： P A H NA P L S I I GY I R 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："P
- 算法：一道题学会位操作和子集运算（LeetCode1178）
算法：一道题学会位操作和子集运算 目录 算法：一道题学会位操作和子集运算 题目 朴素解法 哈希+子集解法 参考 题目 1178. 猜字谜 外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。 字谜的迷面 puzzle 按字符串形式给出，如果一个单词 w
- leetcode刷题笔记-297. 二叉树的序列化与反序列化（java实现）
题目描述 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。 请设计一个算法来实现二叉树的序列化与反序列化。这里不限
- LeetCode 30. 串联所有单词的子串
题目: 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。 示例 1： 输入： s = "barfoothe
- 疑问Leetcode/数组/两数之和
题目 给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1： 输入：nums =
- 【栈和队列】leetcode20——有效的括号
编号20：有效的括号 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1:输入: "()"输出: true
- 剑指 Offer 33. 二叉搜索树的后序遍历序列
剑指 Offer 33. 二叉搜索树的后序遍历序列 Difficulty: 中等 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true ，否则返回 false 。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树： 5 / \ 2 6 / \ 1 3