题目:
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 题解的更多相关文章
-
C++计算二叉树的节点数和高度
用struct结构体的写法: /* * description: 计算二叉树的层数和节点数 * writeby: nick * date: 2012-10-23 16:16 * */ #include ...
-
C递归算法与栈的分析,非全然二叉树遍历分析---ShinePans
对于递归,这里面的分析最好当然是用图形的方式来分析了.这里来总结一下 1.首先对于栈的理解: 先进后出,后进先出 先进后出 2.在进行非全然二叉树的存储之后,我们要做的是对其 ...
-
二叉树遍历等基本操作(Java实现)
前中后序遍历递归实现+层序遍历: 树的结点类代码: public class TreeNode<Value extends Comparable<? super Value>> ...
-
李洪强iOS经典面试题35-按层遍历二叉树的节点
李洪强iOS经典面试题35-按层遍历二叉树的节点 问题 给你一棵二叉树,请按层输出其的节点值,即:按从上到下,从左到右的顺序. 例如,如果给你如下一棵二叉树: 3 / \ 9 20 ...
-
求二叉树第K层的节点个数+求二叉树叶子节点的个数
size_t _FindLeafSize(Node* root) //求二叉树叶子节点的个数 { //static size_t count = 0; if ...
-
面试常见二叉树算法题集锦-Java实现
1.求二叉树的深度或者说最大深度 /* ***1.求二叉树的深度或者说最大深度 */ public static int maxDepth(TreeNode root){ if(root==null) ...
-
六:二叉树中第k层节点个数与二叉树叶子节点个数
二叉树中第k层节点个数 递归解法: (1)假设二叉树为空或者k<1返回0 (2)假设二叉树不为空而且k==1.返回1 (3)假设二叉树不为空且k>1,返回左子树中k-1层的节点个数与右子树 ...
-
R语言:计算现金工资的币数
新入职的员工,有的没有相应银行卡,需要计算现金工资的币数.实发工资,一般取整数. 简化计算,纸币面值只有100.10.1.4278除以100等于42余78,78除以10等于7余8,8除以1等于8. 复 ...
-
LeetCode222——Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes. Definition of a complete binary tree from W ...
随机推荐
-
php上传$_FILES 无法取值
无法取值的主要原因在form. 代码 <form method="post" action="****" name="theForm" ...
-
XML相关操作
一.简单介绍 using System.Xml; //初始化一个xml实例 XmlDocument xml=new XmlDocument(); //导入指定xml文件 xml.Load(path); ...
-
2016年11月8日 星期二 --出埃及记 Exodus 19:24
2016年11月8日 星期二 --出埃及记 Exodus 19:24 The LORD replied, "Go down and bring Aaron up with you. But ...
-
Split的应用
public string qu(string ss) { string s1 = "" ; string[] s = ss.Split(); for (int i = 0; i ...
-
DataTable Select查询
如果是Excel中数据,空数据为DBNull.Value 查询:dt.Select("name is null") 查询长度:dt.Select("len(convert ...
-
由Nginx的DNS缓存导致的访问404
现象 访问某个URL出现404,而且全站都是404.通过日志查看Nginx的规则也正确,请求被代理到指定位置. 排查 最近针对这个站点没有修改过Nginx配置也没有站点升级.所以应该是其他原因.首先P ...
-
day32 进程
上午: # 1 开启子进程 #target #args # if __name__ == '__main__' #start() # 2.其它的方法: #方法: #terminate() #is_al ...
-
【汤鸿鑫 3D太极】5年目标规划(基本功、套路、实战搏击)
[5年目标]在基本功的基础上,每年完成一个套路或实战搏击的学习研究. [中小学2年]三段九节 + 2套路. [高中的3年]太极十三势 + 1套路 + 推手 + 搏击. 1.中小学阶段-可自学 (1)基 ...
-
ASP.Net中的四种状态保持机制
每个人上网可多有过这样的情况,当我们登陆某个网站时,在登陆的旁边会有一个 "记住我" 的复选框,有的网站还会让用户选择记住我.这个记住我是怎么实现的呢? 其实就用利用的是cooki ...
-
php 中文转拼音,可以只转首字母,可以设置utf8、gbk
<?php class Pinyin { /** * 默认是gb编码,第二个参数随意设置即为utf8编 * @param type $isInitial 是否只返回首字母 * @return t ...