LeetCode 222. 完全二叉树的节点个数(Count Complete Tree Nodes)
2024-08-27 05:06:45
题目描述
给出一个完全二叉树,求出该树的节点个数。
说明:
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例:
输入:
1
/ \
2 3
/ \ /
4 5 6 输出: 6
解题思路
从根节点开始分别判断左右子树的高度:
- 若左子树高度等于右子树,说明左子树一定为满二叉树,可得左子树的总节点个数,然后递归求右子树的节点数;
- 若左子树高度大于右子树,说明右子树一定为满二叉树,可得右子树的总节点个数,然后递归求左子树的节点数。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == NULL) return ;
int left = height(root->left), right = height(root->right);
if(left == right)
return ( << left) + countNodes(root->right);
else
return countNodes(root->left) + ( << right);
}
int height(TreeNode* root){
if(root == NULL)
return ;
return height(root->left) + ;
}
};
最新文章
- ActiveMQ笔记(5):JMX监控
- C/C++ 标准输入输出重定向
- WCF创建RESTService
- Pure.css网格系统学习心得——图片的响应式以及应用填充和边框网格单位的学习
- CCNET+ProGet+Windows Batch搭建全自动的内部包打包和推送及管理平台
- 关于《Swift开发指南》背后的那些事
- [TYVJ] P1030 乳草的入侵
- hdu1172猜数字
- MySQL之乱码问题解决详解
- touchmove Bug 工作遇到
- 线程池与Python中的GIL
- window.open 打开子窗口,关闭所有的子窗口
- c# Winform Chart入门
- day33 锁和队列
- matlab练习程序(点云表面法向量)
- 【Codeforces Round 650】Codeforces #334 (Div. 1)
- java保留字
- mongodb postgresql mysql jsonb对比
- 使用nginx很卡之strace命令
- INNODB引擎概述
热门文章
- Fortify漏洞之Cross-Site Scripting(XSS 跨站脚本攻击)
- Typora数学公式
- Django之模型层2
- 异常-java.util.concurrent.TimeoutException: Futures timed out after [100000 milliseconds]
- 运维开发笔记整理-Request对象与Response对象
- Python中的时间
- Thrift使用入门---RPC服务
- 2020年日期表-python实现
- python打造批量关键词排名查询工具
- element-ui upload组件 onchange事件 传自定义参数