当前位置:网站首页>leetcode刷题:二叉树10(完全二叉树的节点个数)
leetcode刷题:二叉树10(完全二叉树的节点个数)
2022-07-05 19:52:00 【涛涛英语学不进去】
222.完全二叉树的节点个数
给出一个完全二叉树,求出该树的节点个数。
示例 1:
- 输入:root = [1,2,3,4,5,6]
- 输出:6
示例 2:
- 输入:root = []
- 输出:0
示例 3:
- 输入:root = [1]
- 输出:1
提示:
- 树中节点的数目范围是[0, 5 * 10^4]
- 0 <= Node.val <= 5 * 10^4
- 题目数据保证输入的树是 完全二叉树
直接层序遍历查,不失为一种快乐的方法。
package com.programmercarl.tree;
import java.util.ArrayDeque;
import java.util.Deque;
/** * @ClassName CountNodes * @Descriotion TODO * @Author nitaotao * @Date 2022/7/4 10:15 * @Version 1.0 * https://leetcode.cn/problems/count-complete-tree-nodes/ * 222. 完全二叉树的节点个数 **/
public class CountNodes {
public int countNodes(TreeNode root) {
/** * 层序遍历 */
if (root == null) {
return 0;
}
Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
deque.offer(root);
int sum = 0;
while (!deque.isEmpty()) {
int size = deque.size();
while (size > 0) {
root = deque.pop();
sum++;
if (root.left != null) {
deque.offer(root.left);
}
if (root.right != null) {
deque.offer(root.right);
}
size--;
}
}
return sum;
}
}
按照满二叉树的性质,节点数 = 前n-1层节点数 + 最后一层节点数
前n-1层节点数 = 2^(n-1) -1
/** * 根据完全二叉树的性质计算 * * @param root * @return */
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if (leftDepth == rightDepth) {
//如果深度相等,则左边为满二叉树
// leftDepth是从当前子树的头结点开始计算深度,不是两棵树的根结点
// ( 2 ^ leftDepth - 1 ) + 1 1为两棵树的根结点
return ((1 << leftDepth) - 1) + 1 + countNodes(root.right);
} else {
//右子树为满二叉树
return ((1 << rightDepth) - 1) + 1 + countNodes(root.left);
}
}
/** * 从当前子树 开始计算深度 * * @param root * @return */
public int getDepth(TreeNode root) {
int depth = 0;
while (root != null) {
root = root.left;
depth++;
}
return depth;
}
边栏推荐
- 众昂矿业:2022年全球萤石行业市场供给现状分析
- Common operators and operator priority
- Flume series: interceptor filtering data
- Is the education of caiqiantang reliable and safe?
- [Collection - industry solutions] how to build a high-performance data acceleration and data editing platform
- What are general items
- [FAQ] summary of common causes and solutions of Huawei account service error 907135701
- 40000 word Wenshuo operator new & operator delete
- 安信证券在网上开户安全吗?
- That's awesome. It's enough to read this article
猜你喜欢
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
城链科技数字化创新战略峰会圆满召开
Add data to excel small and medium-sized cases through poi
That's awesome. It's enough to read this article
Inventory of the most complete low code / no code platforms in the whole network: Jiandao cloud, partner cloud, Mingdao cloud, Qingliu, xurong cloud, Jijian cloud, treelab, nailing · Yida, Tencent clo
leetcode刷题:二叉树16(路径总和)
Android interview, Android audio and video development
What does software testing do? What are the requirements for learning?
淺淺的談一下ThreadLocalInsecureRandom
随机推荐
秋招字节面试官问你还有什么问题?其实你已经踩雷了
深度学习 卷积神经网络(CNN)基础
Relationship between floating elements and parent and brother boxes
C application interface development foundation - form control (5) - grouping control
软件测试是干什么的?学习有啥要求?
Which securities company is better and which platform is safer for mobile account opening
Where is the operation of new bonds? Is it safer and more reliable to open an account
[C language] string function and Simulation Implementation strlen & strcpy & strcat & StrCmp
Float. The specific meaning of the return value of floattorawintbits is to convert float into byte array
Win10 x64环境下基于VS2017和cmake-gui配置使用zxing以及opencv,并实现data metrix码的简单检测
软件测试工程师是做什么的?待遇前景怎么样?
[FAQ] summary of common causes and solutions of Huawei account service error 907135701
成功入职百度月薪35K,2022Android开发面试解答
多分支结构
redis集群模拟消息队列
Common - Hero Minesweeper
What are general items
安卓面试宝典,2022Android面试笔试总结
再忙不能忘安全
IBM大面积辞退40岁+的员工,掌握这十个搜索技巧让你的工作效率至上提高十倍