当前位置: 首页 > news >正文

【LeetCode每日一题】——662.二叉树最大宽度

文章目录

  • 一【题目类别】
  • 二【题目难度】
  • 三【题目编号】
  • 四【题目描述】
  • 五【题目示例】
  • 六【题目提示】
  • 七【解题思路】
  • 八【时间频度】
  • 九【代码实现】
  • 十【提交结果】

一【题目类别】

  • 广度优先搜索

二【题目难度】

  • 中等

三【题目编号】

  • 662.二叉树最大宽度

四【题目描述】

  • 给你一棵二叉树的根节点 root ,返回树的 最大宽度
  • 树的 最大宽度 是所有层中最大的 宽度
  • 每一层的 宽度 被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的 null 节点,这些 null 节点也计入长度。
  • 题目数据保证答案将会在 32 位 带符号整数范围内。

五【题目示例】

  • 示例 1:
    在这里插入图片描述

    • 输入:root = [1,3,2,5,3,null,9]
    • 输出:4
    • 解释:最大宽度出现在树的第 3 层,宽度为 4 (5,3,null,9) 。
  • 示例 2:
    在这里插入图片描述

    • 输入:root = [1,3,2,5,null,null,9,6,null,7]
    • 输出:7
    • 解释:最大宽度出现在树的第 4 层,宽度为 7 (6,null,null,null,null,null,7) 。
  • 示例 3:
    在这里插入图片描述

    • 输入:root = [1,3,2,5]
    • 输出:2
    • 解释:最大宽度出现在树的第 2 层,宽度为 2 (3,2) 。

六【题目提示】

  • 树中节点的数目范围是 [1, 3000]
  • 100 <= Node.val <= 100

七【解题思路】

  • 其实这道题就是二叉树的层序遍历的变种
  • 值得注意的是需要利用完全二叉树的性质
    • 在完全二叉树中,可以将其节点存储到数组中,并且对于序号为i的节点(节点编号从1开始),其
      • 左子节点的序号为i * 2
      • 右子节点的序号为i * 2 + 1
    • 利用以上性质,我们可以将每一层的二叉树的节点编号,用编号值计算每一层的宽度
    • 当计算出每一层的宽度后,就可以计算得到整个二叉树的最大宽度
  • 具体细节请参考下面的代码

八【时间频度】

  • 时间复杂度: O ( n ) O(n) O(n) n n n为传入的二叉树的节点个数
  • 空间复杂度: O ( n ) O(n) O(n) n n n为传入的二叉树的节点个数

九【代码实现】

  1. Java语言版
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/class Solution {public int widthOfBinaryTree(TreeNode root) {// 最小宽度为1int res = 1;// 初始化队列,queue用于存储当前层节点List<Pair<TreeNode, Integer>> queue = new ArrayList<Pair<TreeNode, Integer>>();queue.add(new Pair<TreeNode, Integer>(root, 1));// 使用广度优先遍历算法计算二叉树的最大高度while (!queue.isEmpty()) {// temp用于存储下一层节点List<Pair<TreeNode, Integer>> temp = new ArrayList<Pair<TreeNode, Integer>>();for (Pair<TreeNode, Integer> pair : queue) {TreeNode node = pair.getKey();int index = pair.getValue();if (node.left != null) {temp.add(new Pair<TreeNode, Integer>(node.left, index * 2));}if (node.right != null) {temp.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));}}// 计算二叉树的最大宽度res = Math.max(res, queue.get(queue.size() - 1).getValue() - queue.get(0).getValue() + 1);queue = temp;}// 返回结果return res;}
}
  1. Python语言版
# 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 = rightclass Solution:def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:# 最小宽度为1res = 1# 初始化队列,queue用于存储当前层节点queue = [[root, 1]]# 使用广度优先遍历算法计算二叉树的最大高度while queue:# temp用于存储下一层节点temp = []for node, index in queue:if node.left:temp.append([node.left, index * 2])if node.right:temp.append([node.right, index * 2 + 1])# 计算二叉树的最大宽度res = max(res, queue[-1][1] - queue[0][1] + 1)queue = temp# 返回结果return res
  1. C语言版
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/// 节点最多3000个
#define MAX_NODE_SIZE 3000// 比较大小
#define MAX(a, b) ((a) > (b) ? (a) : (b));// 利用完全二叉树的性质存储二叉树,node保留了节点的左右子树的关系,index记录节点(在数组中)的位置(索引)
typedef struct
{struct TreeNode* node;unsigned long long index;
} levelNode;int widthOfBinaryTree(struct TreeNode* root)
{// 最小宽度为1unsigned long long res = 1;// 初始化队列,queue用于存储当前层节点,temp用于存储下一层节点levelNode* queue = (levelNode*)malloc(sizeof(levelNode) * MAX_NODE_SIZE);levelNode* temp = (levelNode*)malloc(sizeof(levelNode) * MAX_NODE_SIZE);int queueSize = 0;int tempSize = 0;// 根节点入队列queue[queueSize].node = root;queue[queueSize++].index = 1LL;// 使用广度优先遍历算法计算二叉树的最大宽度while (queueSize > 0){// 将当前节点的所有下一层节点按照完全二叉树的索引值存储tempSize = 0;for (int i = 0; i < queueSize; i++){if (queue[i].node->left){temp[tempSize].node = queue[i].node->left;temp[tempSize++].index = queue[i].index * 2;}if (queue[i].node->right){temp[tempSize].node = queue[i].node->right;temp[tempSize++].index = queue[i].index * 2 + 1;} }// 计算二叉树的最大宽度res = MAX(res, queue[queueSize - 1].index - queue[0].index + 1);// 将存储当前层节点信息的队列重新赋值为存储好的下一层节点的信息队列queueSize = tempSize;levelNode* change = queue;queue = temp;temp = change;}// 返回结果return res;
}

十【提交结果】

  1. Java语言版
    在这里插入图片描述

  2. Python语言版
    在这里插入图片描述

  3. C语言版
    在这里插入图片描述

http://www.lryc.cn/news/427780.html

相关文章:

  • 第二十三节、血量更新逻辑的实现
  • Spring Authorization Server 认证服务器搭建
  • 秋招突击——8/15——知识补充——垃圾回收机制
  • 【iOS】UITableViewCell的重用问题解决方法
  • 开发一个微信小程序商城需要哪些技术栈
  • 望繁信科技荣膺上海市浦东新区博士后创新实践基地称号
  • Nginx--代理与负载均衡(扩展nginx配置7层协议及4层协议方法、会话保持)
  • Ubuntu20.4 系统安装后无wifi图标
  • 牛客网SQL进阶135 :每个6/7级用户活跃情况
  • SQLite3使用接口写入二进制文件
  • 在复杂的数据库架构中,如何优化 SQL 查询以提高性能和减少资源消耗?
  • 【HarmonyOS】端云一体化初始化项目
  • LLM之KG:利用大语言模型(LLM)对文本语料提取概念和概念之间的语义关系进而实现自动构建知识图谱
  • Spring Security 6如何使用?
  • PyTorch深度学习快速入门教程--学习笔记
  • SQLALchemy 分组过滤、子查询
  • 华为od(D卷) 环中最长子串/字符成环找偶数LOX
  • 机器学习--常见算法总结
  • QT 网络聊天室简易版
  • Linux_Shell三剑客grep,awk,sed-08
  • uniapp实现足球数据分析平台移动端H5
  • Redis5优化-Redis
  • Element UI【详解】el-scrollbar 滚动条组件
  • 【精选】基于Python大型购物商城系统(京东购物商城,淘宝购物商城,拼多多购物商城爬虫系统)
  • QT翻金币小游戏(含音频图片文件资源)
  • Linux配置JDK8环境变量
  • Fiddle抓手机app的包
  • Oracle+ASM+High冗余详解及空间计算
  • 如何为 Nextcloud 配置自动数据库备份 - 应用程序
  • child_process.spawn简介