LeetCode222 Count CompleteTree Nodes(计算全然二叉树的节点数) Java 题解

时间:2022-08-30 13:34:41

题目:

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes
inclusive at the last level h.

解题:

假设用常规的解法一个个遍历,就是O(n)时间复杂度 。会不通过,这边就不写O(n)的代码了。由于是全然二叉树,满二叉树有一个性质是节点数等于2^h-1,h为高度,所以能够这样推断节点的左右高度是不是一样,假设是一样说明是满二叉树,就能够用刚才的公式。假设左右不相等就递归计算左右节点。

代码:

public static int countNodes(TreeNode root) {
if(root==null)
return 0;
else {
int left=getLeftHeight(root);
int right=getRightHeight(root);
if(left==right)
return (1<<left)-1;
else {
return countNodes(root.right)+countNodes(root.left)+1;
}
}
} public static int getRightHeight(TreeNode root) {
int height=0;
while(root!=null)
{
height++;
root=root.left;
}
return height; } public static int getLeftHeight(TreeNode root) {
int height=0;
while(root!=null)
{
height++;
root=root.right;
}
return height; }

LeetCode222 Count CompleteTree Nodes(计算全然二叉树的节点数) Java 题解的更多相关文章

  1. C&plus;&plus;计算二叉树的节点数和高度

    用struct结构体的写法: /* * description: 计算二叉树的层数和节点数 * writeby: nick * date: 2012-10-23 16:16 * */ #include ...

  2. C递归算法与栈的分析&comma;非全然二叉树遍历分析---ShinePans

                 对于递归,这里面的分析最好当然是用图形的方式来分析了.这里来总结一下 1.首先对于栈的理解: 先进后出,后进先出 先进后出 2.在进行非全然二叉树的存储之后,我们要做的是对其 ...

  3. 二叉树遍历等基本操作&lpar;Java实现&rpar;

    前中后序遍历递归实现+层序遍历: 树的结点类代码: public class TreeNode<Value extends Comparable<? super Value>> ...

  4. 李洪强iOS经典面试题35-按层遍历二叉树的节点

    李洪强iOS经典面试题35-按层遍历二叉树的节点 问题 给你一棵二叉树,请按层输出其的节点值,即:按从上到下,从左到右的顺序. 例如,如果给你如下一棵二叉树:    3   / \  9  20   ...

  5. 求二叉树第K层的节点个数&plus;求二叉树叶子节点的个数

    size_t _FindLeafSize(Node* root)     //求二叉树叶子节点的个数    {        //static size_t count = 0;        if ...

  6. 面试常见二叉树算法题集锦-Java实现

    1.求二叉树的深度或者说最大深度 /* ***1.求二叉树的深度或者说最大深度 */ public static int maxDepth(TreeNode root){ if(root==null) ...

  7. 六:二叉树中第k层节点个数与二叉树叶子节点个数

    二叉树中第k层节点个数 递归解法: (1)假设二叉树为空或者k<1返回0 (2)假设二叉树不为空而且k==1.返回1 (3)假设二叉树不为空且k>1,返回左子树中k-1层的节点个数与右子树 ...

  8. R语言:计算现金工资的币数

    新入职的员工,有的没有相应银行卡,需要计算现金工资的币数.实发工资,一般取整数. 简化计算,纸币面值只有100.10.1.4278除以100等于42余78,78除以10等于7余8,8除以1等于8. 复 ...

  9. LeetCode222——Count Complete Tree Nodes

    Given a complete binary tree, count the number of nodes. Definition of a complete binary tree from W ...

随机推荐

  1. php上传&dollar;&lowbar;FILES 无法取值

    无法取值的主要原因在form. 代码 <form method="post" action="****" name="theForm" ...

  2. XML相关操作

    一.简单介绍 using System.Xml; //初始化一个xml实例 XmlDocument xml=new XmlDocument(); //导入指定xml文件 xml.Load(path); ...

  3. 2016年11月8日 星期二 --出埃及记 Exodus 19&colon;24

    2016年11月8日 星期二 --出埃及记 Exodus 19:24 The LORD replied, "Go down and bring Aaron up with you. But ...

  4. Split的应用

    public string qu(string ss) { string s1 = "" ; string[] s = ss.Split(); for (int i = 0; i ...

  5. DataTable Select查询

    如果是Excel中数据,空数据为DBNull.Value 查询:dt.Select("name is null") 查询长度:dt.Select("len(convert ...

  6. 由Nginx的DNS缓存导致的访问404

    现象 访问某个URL出现404,而且全站都是404.通过日志查看Nginx的规则也正确,请求被代理到指定位置. 排查 最近针对这个站点没有修改过Nginx配置也没有站点升级.所以应该是其他原因.首先P ...

  7. day32 进程

    上午: # 1 开启子进程 #target #args # if __name__ == '__main__' #start() # 2.其它的方法: #方法: #terminate() #is_al ...

  8. 【汤鸿鑫 3D太极】5年目标规划(基本功、套路、实战搏击)

    [5年目标]在基本功的基础上,每年完成一个套路或实战搏击的学习研究. [中小学2年]三段九节 + 2套路. [高中的3年]太极十三势 + 1套路 + 推手 + 搏击. 1.中小学阶段-可自学 (1)基 ...

  9. ASP&period;Net中的四种状态保持机制

    每个人上网可多有过这样的情况,当我们登陆某个网站时,在登陆的旁边会有一个 "记住我" 的复选框,有的网站还会让用户选择记住我.这个记住我是怎么实现的呢? 其实就用利用的是cooki ...

  10. php 中文转拼音,可以只转首字母,可以设置utf8、gbk

    <?php class Pinyin { /** * 默认是gb编码,第二个参数随意设置即为utf8编 * @param type $isInitial 是否只返回首字母 * @return t ...