当前位置:网站首页>Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)
Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)
2022-07-05 19:59:00 【Taotao can't learn English】
222. The number of nodes in a complete binary tree
Give a completely binary tree , Find out the number of nodes of the tree .
Example 1:
- Input :root = [1,2,3,4,5,6]
- Output :6
Example 2:
- Input :root = []
- Output :0
Example 3:
- Input :root = [1]
- Output :1
Tips :
- The number of nodes in the tree ranges from [0, 5 * 10^4]
- 0 <= Node.val <= 5 * 10^4
- The topic data ensures that the input tree is Perfect binary tree
Direct sequence traversal search , It can be regarded as a happy method .
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. The number of nodes in a complete binary tree **/
public class CountNodes {
public int countNodes(TreeNode root) {
/** * Sequence traversal */
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;
}
}
According to the properties of full binary tree , Number of nodes = front n-1 Number of layer nodes + Number of nodes in the last layer
front n-1 Number of layer nodes = 2^(n-1) -1
/** * According to the properties of complete binary tree * * @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) {
// If the depth is equal , Then the left side is full of binary trees
// leftDepth Is to calculate the depth from the head node of the current subtree , Not the root node of two trees
// ( 2 ^ leftDepth - 1 ) + 1 1 It is the root node of two trees
return ((1 << leftDepth) - 1) + 1 + countNodes(root.right);
} else {
// The right subtree is a full binary tree
return ((1 << rightDepth) - 1) + 1 + countNodes(root.left);
}
}
/** * From current subtree Start to calculate the depth * * @param root * @return */
public int getDepth(TreeNode root) {
int depth = 0;
while (root != null) {
root = root.left;
depth++;
}
return depth;
}
边栏推荐
- leetcode刷题:二叉树16(路径总和)
- 建立自己的网站(16)
- Summer Challenge harmonyos - realize message notification function
- 浅浅的谈一下ThreadLocalInsecureRandom
- C langue OJ obtenir PE, ACM démarrer OJ
- Debezium series: idea integrates lexical and grammatical analysis ANTLR, and check the DDL, DML and other statements supported by debezium
- leetcode刷题:二叉树18(最大二叉树)
- Information / data
- DP:树DP
- Go language | 03 array, pointer, slice usage
猜你喜欢
如何安全快速地从 Centos迁移到openEuler
After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
leetcode刷题:二叉树18(最大二叉树)
Database logic processing function
Recommended collection, my Tencent Android interview experience sharing
解决Thinkphp框架应用目录下数据库配置信息修改后依然按默认方式连接
淺淺的談一下ThreadLocalInsecureRandom
浅浅的谈一下ThreadLocalInsecureRandom
【硬核干货】数据分析哪家强?选Pandas还是选SQL
Debezium series: record the messages parsed by debezium and the solutions after the MariaDB database deletes multiple temporary tables
随机推荐
通过POI追加数据到excel中小案例
Redis cluster simulated message queue
leetcode刷题:二叉树12(二叉树的所有路径)
Is the education of caiqiantang reliable and safe?
DP:树DP
【c语言】快速排序的三种实现以及优化细节
C#应用程序界面开发基础——窗体控制(5)——分组类控件
The city chain technology Digital Innovation Strategy Summit was successfully held
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
C application interface development foundation - form control (5) - grouping control
Go language | 03 array, pointer, slice usage
Postman core function analysis - parameterization and test report
[C language] merge sort
Is it safe for Guosen Securities to open an account online?
Debezium series: modify the source code to support UNIX_ timestamp() as DEFAULT value
Concept and syntax of function
webuploader文件上传 拖拽上传 进度监听 类型控制 上传结果监听控件
How to select the Block Editor? Impression notes verse, notation, flowus
C langue OJ obtenir PE, ACM démarrer OJ
95后阿里P7晒出工资单:狠补了这个,真香...