首页 > 编程语言 >算法20:求二叉树最宽的层有多少个节点(层序遍历续)

算法20:求二叉树最宽的层有多少个节点(层序遍历续)

时间:2023-02-22 11:14:10浏览次数:52  
标签:遍历 TreeNode 层序 二叉树 new 20 节点 left

 之前我们已经实现了二叉树的层序遍历算法8:LeetCode_二叉树的层序遍历_chen_yao_kerr的博客-CSDN博客

和二叉树的序列化与反序列化算法19:LeetCode_二叉树序列化与反序列化(层序)_chen_yao_kerr的博客-CSDN博客他们都是用到了二叉树的层序遍历相关知识,下面再来看一个关于二叉树层序遍历的算法题:

 

题目:二叉树通常有很多层,每一层的节点数量有可能都是不同的,设计一种算法,找到二叉树的最宽的层一共有多少节点

package code03.二叉树_02;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 求二叉树最宽的层有多少个节点
 */
public class Code02_TreeMaxWidth {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    //

    /**
     * 二叉树层序遍历
     * 基本思路就是每一层遍历完以后,统计当前层数的节点数,
     * 然后根之前的节点最大值做比较,一直更新宽度最大值
     * 最终返回的就是二叉树最大层中节点的个数
     */
    public int maxWidth(TreeNode root)
    {
        //边界值判断
        if (root == null) {
            return 0;
        }

        //逐层搜集,首先收集根节点,并存入队列。印证思路第1步
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int max = 0;                //当前已经统计完最宽层的节点数
        int curLevelNodes = 0;      //当前层的节点数
        TreeNode curEnd = root;     //本层结束节点
        TreeNode nextEnd = null;    //下一层结束节点
        TreeNode cur = null;

        while (!queue.isEmpty())
        {
            cur = queue.poll();
            if (cur.left != null)
            {
                queue.add(cur.left);
                nextEnd = cur.left;
            }

            if (cur.right != null)
            {
                queue.add(cur.right);
                nextEnd = cur.right;
            }

            curLevelNodes++;
            //当前层最后一个节点,代表当前层已经全部遍历结束
            if (cur == curEnd) {
                //当前层的结束节点切换到下一层结束节点处,为下一层节点遍历做准备
                curEnd = nextEnd;
                //之前层节点数的最大值 和 当前层节点数比较,得到最新的最宽层的节点数
                max = Math.max(curLevelNodes, max);
                //重置当前层的节点数,为下一层做准备
                curLevelNodes = 0;
            }
        }

        return max;
    }

    public static void main(String[] args) {

        TreeNode tree = new TreeNode(1);
        tree.left = new TreeNode(2);
        tree.right = new TreeNode(3);
        tree.left.left = new TreeNode(4);
        tree.left.right = new TreeNode(5);
        tree.right.left = new TreeNode(6);
        tree.right.right = new TreeNode(7); //最大层的宽度为 4
        tree.left.left.left = new TreeNode(8);

        Code02_TreeMaxWidth test = new Code02_TreeMaxWidth();
        int with = test.maxWidth(tree);
        System.out.println("最大宽度为 :" + with);
    }
}

 

 

标签:遍历,TreeNode,层序,二叉树,new,20,节点,left
From: https://www.cnblogs.com/chen1-kerr/p/17143630.html

相关文章

  • C/C++书籍借阅系统[2023-02-22]
    C/C++书籍借阅系统[2023-02-22]1.程序名称:书籍借阅系统2.课题来源:课程组自拟3.课题类型:综合型4.目的和意义:1)综合运用所学知识,解决实际问题2)全面提高学生的程序设计......
  • 【2023-02-21】思考改进
    20:00最大的决心会产生最高的智慧。                                         ......
  • 2019年,愿遇见更好的自己,加油!
    新年伊始,仔细想了想,给自己立下了如下几个flag,总的来说,希望技术上有所积累,身体更健壮,眼界更进一步拓宽,赚钱的门路再新增一条:1、学好Linux基础,并能自主做一个以Linux为平台的......
  • 春秋云镜-CVE-2022-30887
    春秋云镜-CVE-2022-30887多语言药房管理系统(MPMS)是用PHP和MySQL开发的,该软件的主要目的是在药房和客户之间提供一套接口,客户是该软件的主要用户。该软件有助于......
  • 【LeetCode二叉树#03】翻转二叉树的几种方法
    翻转二叉树力扣题目链接(opensnewwindow)翻转一棵二叉树。这道题目背后有一个让程序员心酸的故事,听说Homebrew的作者MaxHowell,就是因为没在白板上写出翻转二叉树,最......
  • 【YBT2023寒假Day12 B】仰望星空(DP)(线段树)(笛卡尔树)
    仰望星空题目链接:YBT2023寒假Day12B题目大意有一个n*n的网格,第i列下面的ai个点都是障碍。然后又一些不是障碍的地方有特殊点,删掉它有费用。要你用最小费用使得......
  • .NET周报 【2月第3期 2023-02-18】
    国内文章2023年.NET仓库社区年度调查已经开始https://mp.weixin.qq.com/s/H9xUAO_yAdqm5CIHBs_eqA中国地区是.NET的一个重要的市场和社区,有着众多的.NET开发者和爱......
  • 【YBT2023寒假Day12 A】我的世界(二分)(主席树)
    我的世界题目链接:YBT2023寒假Day12A题目大意有n个数,每一秒每个数都会减小1,而且你可以选一个数让它减小x,小于0的数会变成0。给你s秒,问你s秒操作后所有数中......
  • 公众号文章怎么携带文件?2023最新解决办法
    我们在日常生活中,经常会看到公众号发布的一些图文、音频、视频等,有的时候更是能在文章中看到并下载一些附件文件,比如:申请表、报名表、登记表等文档。公众号文章作为一......
  • 2023年2月22日学习Linux:计算机操作系统
    .计算机操作系统简介1)掌握操作系统的定义:操作系统是一个用来协调、管理和控制计算机硬件和软件资源的系统程序,它位于硬件和应用程序之间。、2)掌握操作系统的内核的定......