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

作者:神秘网友 发布时间:2021-02-27 12:20:13

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】 相关文章

  1. LeetCode | 0655. 输出二叉树【Python】

    问题 力扣 在一个 m*n 的二维字符串数组中输出二叉树,并遵守以下规则: 行数 m 应当等于给定二叉树的高度。 列数 n 应当总是奇数。 根节点的值(以字符串格式给出)应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分(左下部分和

  2. 【栈和队列】leetcode150——逆波兰表达式求值

    编号150: 逆波兰表达式求值 根据 逆波兰表示法 ,求表达式的值。 有效的运算符包括 + , - , * , / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 说明: 整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值

  3. 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

  4. [Leetcode]6. Z 字形变换

    题目描述 将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行Z 字形排列。 比如输入字符串为 "PAYPALISHIRING"行数为 3 时,排列如下: P A H NA P L S I I GY I R 之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"P

  5. 算法:一道题学会位操作和子集运算(LeetCode1178)

    算法:一道题学会位操作和子集运算 目录 算法:一道题学会位操作和子集运算 题目 朴素解法 哈希+子集解法 参考 题目 1178. 猜字谜 外国友人仿照中国字谜设计了一个英文版猜字谜小游戏,请你来猜猜看吧。 字谜的迷面 puzzle 按字符串形式给出,如果一个单词 w

  6. leetcode刷题笔记-297. 二叉树的序列化与反序列化(java实现)

    题目描述 序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。 请设计一个算法来实现二叉树的序列化与反序列化。这里不限

  7. LeetCode 30. 串联所有单词的子串

    题目: 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。 示例 1: 输入: s = "barfoothe

  8. 疑问Leetcode/数组/两数之和

    题目 给定一个整数数组 nums和一个整数目标值 target,请你在该数组中找出 和为目标值 的那两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1: 输入:nums =

  9. 【栈和队列】leetcode20——有效的括号

    编号20:有效的括号 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1:输入: "()"输出: true

  10. 剑指 Offer 33. 二叉搜索树的后序遍历序列

    剑指 Offer 33. 二叉搜索树的后序遍历序列 Difficulty: 中等 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树: 5 / \ 2 6 / \ 1 3

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词