二叉树宽度计算层序实战:掌握最大变量节点数的统计技巧

千辰姑娘_3053

千辰姑娘_3053

2026-05-10

182人浏览

原创

二叉树的宽度指所有层中真实节点数量的最大值,通过层序遍历中每次记录队列长度获取每层节点数,边遍历边更新最大值,空树返回0,单节点树宽度为1。

二叉树的“宽度”通常指**所有层中节点数量的最大值**,也就是某一层里实实在在存在的非空节点个数最多是多少。这和 LeetCode 662 题中的“最大宽度”(含虚拟空位编号差)不同——这里只统计真实存在的节点,不考虑结构空缺。 掌握这个统计,关键在**层序遍历过程中的节点计数控制**,而不是堆栈或递归深度。下面直接说实用技巧:

用队列大小动态抓取每层节点数

层序遍历时,每轮处理前先记下当前队列长度,它就等于「本层真实节点数」:

  • 根节点入队后,队列长度为 1 → 第一层有 1 个节点
  • 处理完这一轮(出队 1 次),把它的左右孩子(若存在)都入队 → 新入队节点全属于下一层
  • 下一轮开始前,再读队列长度 → 就是第二层的节点总数

无需额外变量标记层数、无需哈希表存层级映射,靠队列长度本身就能精准分层。

边遍历边更新最大值,一次到位

每处理完一层,就把当前层节点数和已知最大值比较并更新:

  • 初始化 maxWidth = 0
  • 每层结束时:maxWidth = Math.max(maxWidth, 当前层节点数)
  • 遍历完毕即得答案,无须事后扫描

注意边界:空树返回 0,单节点树宽度为 1

代码开头加判空即可,避免后续逻辑异常:

  • if (root == null) return 0;
  • 队列初始只加 root,后续仅对非空子节点入队
  • 这样天然过滤掉 null 节点,计数完全反映真实结构

参考精简实现(Java)

以下逻辑清晰、无冗余状态:

public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    Queue<treenode> queue = new LinkedList();
    queue.offer(root);
    int maxWidth = 0;
    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // 当前层真实节点数
        maxWidth = Math.max(maxWidth, levelSize);
        for (int i = 0; i </treenode>
PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2741

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

376

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

417

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

492

25

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

6536

4

Uvicorn 报错与问题解决教程
Uvicorn 报错与问题解决教程

本专题汇总了Uvicorn服务器常见问题与报错解决的教程合集,涵盖启动失败、端口占用、模块导入错误、事件循环冲突及热重载失效等典型故障的排查思路。同时整理了多进程与Worker配置、SSL/HTTPS证书报错、跨域与代理配置等实战解决方案,助你快速定位并解决Uvicorn运行中的各类问题。

2026.11.02

0

14

Uvicorn使用教程
Uvicorn使用教程

本专题汇总了Uvicorn使用教程与启动运行指南,涵盖其作为Python ASGI服务器的定位与特点,以及命令行启动(uvicorn main:app --reload)、参数配置(host/port/workers)、程序内嵌运行与Gunicorn结合部署等核心用法。同时整理了热重载调试、日志配置与生产环境部署优化等技巧,助你快速掌握Uvicorn的运行与配置。

2026.11.02

0

17

Uvicorn安装配置教程
Uvicorn安装配置教程

本专题汇总了Uvicorn的安装配置教程与部署指南,涵盖通过pip安装Uvicorn、启动FastAPI/Starlette应用、开发模式热重载(--reload)及多进程工作模式配置等核心操作。同时整理了结合Gunicorn的生产部署方案、HTTPS与反向代理配置及性能调优技巧,助你快速完成Uvicorn服务的安装与上线部署。

2026.11.02

0

17

Vite 项目如何打包和部署
Vite 项目如何打包和部署

Vite项目打包部署专题汇集生产构建、产物预览、输出目录、资源路径、Nginx与GitHub Pages部署及常见白屏和路由404问题的已审核文章,帮助读者完成上线流程。

2026.10.28

100

16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.1万人学习