[nowCoder] 完全二叉树结点数
2024-10-19 09:34:07
给定一棵完全二叉树的头节点head,返回这棵树的节点个数。如果完全二叉树的节点数为N,请实现时间复杂度低于O(N)的解法。
分析:遍历的话不管是前序、中序、后序还是层次都是O(N),低于O(N)只能是O(lgN),向二分方向努力。
完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。
只有最后一层不满,我们可以根据左子树的最右节点或者右字数的最左节点来判断左子树是不是满二叉树,
若左字树满,可用公式计算左字树的节点数2^(l-1), 总节点数n= 2^(l-1)+ 1(根节点)+递归右子树的节点数。
若左字树不满,可知右子树满,层数为l-2,可用公式计算左字树的节点数2^(l-2), 总节点数n= 2^(l-2)+ 1(根节点)+递归左子树的节点数。
判断左子树的最右节点或者右字数的最左节点是否存在可以从层数上来判断。。
class Solution {
private:
int calcHeight(TreeNode *head)
{
int height = ;
while(head)
{
head = head->left;
height ++;
}
return height;
}
public:
int nodeNum(struct TreeNode* head)
{
if(head == NULL)
return ; int height = calcHeight(head);
//cout << "height\t" <<height << endl; if(calcHeight(head->right) == height - )//left sub-tree is full
return ( << (height - ) )+ nodeNum(head->right);
else// right sub-tree is full
return ( << (height - ) )+ nodeNum(head->left);
}
};
最新文章
- 【转】C++格式化输出
- URAL 1992 CVS 可持久化链栈
- cobbler重装、web、定制化
- border-radius
- Java如何将html转以后的字符转化成正常显示的字符
- iOS 开发UI篇 -- 懒加载学习
- 4项技巧使你不再为PHP中文编码苦恼
- JQ 选择器大全
- jinja2 宏的简单使用总结(macro)
- MongoDB 的 MapReduce 大数据统计统计挖掘
- 第八届河南省赛D.引水工程(kruthcra+prime)
- matlab画棋盘格程序
- Python给多个变量赋值
- Number Complement
- Azure IoT Edge on Raspberry Pi 3 with Raspbian
- YARN详解
- 如何实现一个基于 jupyter 的 microservices
- PYTHON-迭代器,xxx生成式
- 利用OCR识别扫描的jpg、tif文件的文字
- shiro中authc和user的权限区别