力扣labuladong一刷day40天计算完全二叉树节点数

这篇具有很好参考价值的文章主要介绍了力扣labuladong一刷day40天计算完全二叉树节点数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

力扣labuladong一刷day40天计算完全二叉树节点数

一、222. 完全二叉树的节点个数

题目链接:https://leetcode.cn/problems/count-complete-tree-nodes/
思路:计算完全二叉树直接全遍历的话很浪费时间,但是可以利用完全二叉树的特性来解题, 每到一个节点我们就计算它的left = node.left深度,和right=node.right的深度,如果这两个深度想等,总节点的个数就是2的h次方-1,如果不相等那就把当前节点计数,然后递归左右子树执行上面的,每次左右子树都会有一个可以大化小,小化无。文章来源地址https://www.toymoban.com/news/detail-759459.html

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode l = root, r = root;
        int a = 0, b = 0;
        while (l != null) {
            l = l.left;
            a++;
        }
        while (r != null) {
            r = r.right;
            b++;
        }
        if (a == b) {
            return (int)Math.pow(2, a) - 1;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

到了这里,关于力扣labuladong一刷day40天计算完全二叉树节点数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣labuladong——一刷day97

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 首先,动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等

    2024年01月22日
    浏览(48)
  • 力扣labuladong一刷day63天单词拆分

    力扣labuladong一刷day63天单词拆分 一、139. 单词拆分 题目链接:https://leetcode.cn/problems/word-break/description/ 思路:s是否能被拆分成字典中的单词,单词数量是不限的,故是完全背包问题,不限数量的单词是否能组成字符串s,可以看的出来,并不是要求你长度相等就可以,还得有

    2024年01月21日
    浏览(35)
  • 力扣labuladong一刷day59天动态规划

    力扣labuladong一刷day59天动态规划 一、509. 斐波那契数 题目链接:https://leetcode.cn/problems/fibonacci-number/description/ 思路:这是非常典型的一道题,下面是优化过的代码,a,b就是dp数组,因为每计算一个值,需要前两个值,这个a,b就是用来记录前两个值,避免重复计算,递推公式便

    2024年01月21日
    浏览(49)
  • 力扣labuladong一刷day39天最近公共祖先问题

    力扣labuladong一刷day39天最近公共祖先问题 一、236. 二叉树的最近公共祖先 题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 思路:寻找最近公共祖先,在前序的位置判断,如果找到一个就返回,然后在后序的位置收尾,即左右子树都遍历过了,如果都找到的话

    2024年02月04日
    浏览(38)
  • 完全二叉树、完美二叉树、完满二叉树、计算完全二叉树的结点

    对于完美二叉树,我们常用的是另一个名称:满二叉树 完美二叉树的定义: 完美二叉树是一种特殊的完全二叉树,每层都是满的,像一个稳定的三角形 完全二叉树的定义: 全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。

    2023年04月08日
    浏览(82)
  • 算法训练day16Leetcode104二叉树最大深度111二叉树最小深度222完全二叉树的节点个数

    https://www.bilibili.com/video/BV1Gd4y1V75u/?vd_source=8272bd48fee17396a4a1746c256ab0ae 用递归,但是什么顺序没想清楚 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始) 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边

    2024年01月16日
    浏览(44)
  • day16 二叉树的最大深度 n叉树的最大深度 二叉树的最小深度 完全二叉树的节点数

    题目链接:104 二叉树的最大深度 题意 二叉树的根节点是root,返回其最大深度(从根节点到最远叶子节点的最长路径上的节点数) 递归 根节点的的高度就是二叉树的最大深度  所以使用后序遍历求最大高度的方式求出最大深度 递归三部曲 1)确定递归函数的参数和返回值

    2024年02月02日
    浏览(46)
  • 算法刷题Day 16 二叉树的最大深度+N叉树的最大深度+二叉树的最小深度+完全二叉树的节点个数

    递归法 迭代法 使用层序的方法,相对比较好理解 递归法 迭代法 跟二叉树的迭代差不多意思。 要想到是后序遍历 递归法 先计算左右两棵子树的节点数,再加和,用后序遍历的方法 迭代法 迭代法用层序遍历来处理 适用于完全二叉树的优化 完全二叉树优化方法没自己想出来

    2024年02月17日
    浏览(40)
  • 代码随想录 Day13 二叉树 LeetCode T104 二叉树的最大深度 T111 二叉树的最小深度 T222完全二叉树的节点个数

    以下题解的更详细思路来自于:代码随想录 (programmercarl.com) 二叉树的高度与深度 这里先补充一下二叉树深度和高度的概念 高度:二叉树中任意一个节点到叶子结点的距离 深度:二叉树中任意一个节点到根节点的距离 下面给出一个图便于理解 获取高度与深度的遍历方式 高度:后

    2024年02月08日
    浏览(41)
  • 初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)

    本篇博客是初阶数据结构树的收尾,将会讲掉 基本二叉树链式结构的具体内容和实现,包括二叉树的构建,前序遍历,中序遍历,后序遍历和层序遍历,计算二叉树结点个数,第k层结点个数,二叉树叶子结点个数,以及判断一个二叉树是否为完全二叉树 。话不多说,开始我

    2024年03月24日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包