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。
热门推荐
内置风扇成新宠，曝三家 TOP5 手机厂商测试主动散热新机
如何收集证据以支持裁员赔偿申请
劳动者怎么能领到补偿金
经常手麻警惕9种疾病风险
如何识别和处理代码中的潜在安全风险
“三年涨薪七次”，京东凭什么
心理咨询的过程是怎样的 心理咨询疗法有哪些
鸡皮能吃吗？医生的专业解答来了
经常喝茶好处多，一文告诉你：什么体质喝什么茶，你喝对了吗？
圆肩驼背要练菱形肌
圆肩驼背怎么矫正
选购面霜攻略：解析关键护肤成分
鸡蛋和鸡胸肉哪个更有营养？
退休金如何达标？灵活就业者必看：缴多少年能在深圳领到2520元？
健康生活，房颤为何还会找上门？
奔驰GLC300燃油压力过低故障诊断与排除
专业要账技巧：这些话术让欠款无处可逃
网名id小众高级（精选110个）
如何在人际交往中保护自己的隐私
如何将知识转化为智慧？从阅读到实践的完整指南
人类DNA的快速进化让我们拥有了最强大脑
四肢末梢冰凉怎么调理
经济基础与上层建筑的矛盾运动及其规律
什么是氢气安全
【生活妙招】回南天来袭！该如何应对？拒绝潮湿，学会这套连招，衣服干爽、家里不湿！
去烘焙店买面包时，这4种一定要少买！烘焙师：只有不懂的人才会吃
经济基础与上层建筑的矛盾运动及其规律
鼓膜内陷怎么办？严重吗？能治好吗？
19张图，探索黄金投资的奥秘
DDR内存技术深度解析：四大核心技术如何提升内存速度