LeetCode 222.完全二叉树的节点个数
创作时间:
作者:
@小白创作中心
LeetCode 222.完全二叉树的节点个数
引用
CSDN
1.
https://m.blog.csdn.net/weixin_50878507/article/details/143139512
题目描述
给你一棵完全二叉树的根节点root，求出该树的节点个数。
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层，则该层包含1~ 2^h个节点。
示例 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- 题目数据保证输入的树是完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为O(n)的简单解决方案。你可以设计一个更快的算法吗？
思路
按照普通二叉树的思路来求解：
递归法
使用后序遍历
递归三部曲：
- 确定递归函数的参数和返回值。参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
- 确定终止条件。如果为空节点的话，就返回0，表示节点数为0。
- 确定单层递归的逻辑。先求左子树的节点数量，再求右子树的节点数量，最后取总和再加一（加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
时间复杂度：O(n)
迭代法
只需要稍微改动一下模版，将变量result用于统计节点数量即可。
时间复杂度：O(n)
按照完全二叉树的特性来求解：
递归法
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层，则该层包含1~ 2^(h-1)个节点。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用2^树深度 - 1来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
在完全二叉树中，如果递归向左外遍历的深度等于递归向右外遍历的深度，那说明就是满二叉树，否则不是满二叉树。
本方法的巧妙之处在于计算左外侧深度（一直往左）和右外侧深度（一直往右）时，中间的节点是不需要遍历的，这样就节省了时间，而且能够直接使用满二叉树的公式来计算节点数量。
终止条件：
- 如果为空节点的话，就返回0，表示节点数为0。
- 如果是满二叉树的话，就返回满二叉树的节点数：2^树深度 - 1。
代码
C++版：
方法一：递归法（后序遍历）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 递归法，后序遍历
int dfs(TreeNode* node){
if(node==NULL) return 0;
int leftNum=dfs(node->left); // 左
int rightNum=dfs(node->left); // 右
int sum=1+leftNum+rightNum; // 中
return sum;
}
int countNodes(TreeNode* root) {
return dfs(root);
}
};
方法二：迭代法（层序遍历）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 迭代法，层序遍历
int countNodes(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
int result = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
result++; // 记录节点数量
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
方法三：按照完全二叉树的特性来求解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 递归法，利用完全二叉树的特性，后序遍历
int dfs(TreeNode* node){
// 终止条件
if(node==NULL) return 0;
TreeNode* left=node->left;
TreeNode* right=node->right;
int leftHeight=0;
int rightHeight=0;
// 统计左侧深度
while(left){
left=left->left;
leftHeight++;
}
// 统计右侧深度
while(right){
right=right->right;
rightHeight++;
}
// 另外一个终止条件：遇到满二叉树
if(leftHeight==rightHeight){
// 位运算，向左移leftHeight位，相当于2的(leftHeight+1)次方
return (2<<leftHeight)-1;
}
int leftNum = dfs(node->left); // 左
int rightNum = dfs(node->right); // 右
int sum = leftNum + rightNum + 1; // 中
return sum;
}
int countNodes(TreeNode* root) {
return dfs(root);
}
};
Python版：
方法一：递归法（后序遍历）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# 递归法，后序遍历
def getNodesNum(self, cur):
if not cur:
return 0
leftNum = self.getNodesNum(cur.left) #左
rightNum = self.getNodesNum(cur.right) #右
treeNum = leftNum + rightNum + 1 #中
return treeNum
def countNodes(self, root: Optional[TreeNode]) -> int:
return self.getNodesNum(root)
方法二：迭代法（层序遍历）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# 迭代法，层序遍历
def countNodes(self, root: Optional[TreeNode]) -> int:
queue = collections.deque()
if root:
queue.append(root)
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
result += 1 #记录节点数量
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
方法三：按照完全二叉树的特性来求解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# 递归法，利用完全二叉树的特性，后序遍历
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
left = root.left
right = root.right
leftHeight = 0
rightHeight = 0
while left: #求左子树深度
left = left.left
leftHeight += 1
while right: #求右子树深度
right = right.right
rightHeight += 1
if leftHeight == rightHeight:
return (2 << leftHeight) - 1
return self.countNodes(root.left) + self.countNodes(root.right) + 1
需要注意的地方
leftHeight和rightHeight初始化为0是为了能够让下面求指数变得方便（可以使用位运算），如果不使用位运算的话应初始化为1。
热门推荐
西宁眼科医疗资源概览：探寻备受赞誉的眼科医院与医生
微信朋友圈的高级玩法：让你的动态更吸引人
如何提前布局热点板块以捕捉市场机会？这些布局策略对投资者有何指导意义？
对肾无伤害的消炎药
李白被称为什么诗人？他的诗有何特色？
喝酒怎么不容易醉
层次分析法（AHP）：一种综合评价及决策方法
怎样评估风险管理体系的有效性和成熟度？
福建大专显示暂无录取信息？别慌！几种可能原因和解决办法🔍
怎么查询国外留学申请结果？申请状态如何查看？
损伤防治：髋部撞击症
青岛周边游攻略：10大必去景点+美食地图
鸽巢问题优秀教学实录（精选5篇）
八字金不换——余氏调候用神表（收藏）
2025年中国氨咖黄敏胶囊行业深度分析：市场规模、竞争格局与发展趋势
WiFi信号死角怎么办？路由器摆放与优化全攻略
数数数学中的数
史上当皇帝当得最爽的是哪位？
江苏十大特色名小吃，江苏美食甲天下，你吃过几个？
牙周脓肿怎么处理好得快？这篇指南将为你详细讲解从紧急清洁的每一步
婚内财产协议需要什么证件和手续才有效
金价跳水！专家解析未来走势
50亿元！光刻机工厂正式落地，国产技术要开始“崛起”了
小米汽车欧洲大动作！宝马15年老将领衔，加速电动车研发进程
国产精品一二三产区区别：如何根据不同产区选购高品质商品
国产精品999：探索国产商品的独特魅力与消费趋势的深度分析
小小腌菜藏大学问 健康食用有妙招
以“怪”出圈的网红饮料背后竟是个百年品牌
陈陶《陇西行》：全诗表达了作者内心中的非战情绪
如何用虚拟机搭建PHP开发环境