完全二叉树的节点个数
# 📃 题目描述
题目链接:222. 完全二叉树的节点个数 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点
示例 1:
输入:root = [1,2,3,4,5,6]
输出:6
示例 2:
输入:root = []
输出:0
示例 3:
输入:root = [1]
输出:1
# 🔔 解题思路
# 迭代法
最简单最容易想到,就是直接迭代遍历一遍这个二叉树,在遍历过程中记录节点的数量就可以了,这里给出层序遍历的解法:
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
// 二叉树节点个数
int res = 0;
Queue<TreeNode> queue = new LinkedList<>();
// 根节点入队
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i ++) {
TreeNode cur = queue.poll();
res ++;
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
return res;
}
}
# 递归法
用递归来做也可以,参考上一题 104. 二叉树的最大深度 - 力扣(LeetCode) (leetcode-cn.com) (opens new window),用递归后序遍历,先递归获取左子树的节点个数,再递归获取右子树的节点个数,然后两者相加再加 1,就是整个二叉树的节点个数
class Solution {
public int countNodes(TreeNode root) {
// 递归出口
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int leftSize = countNodes(root.left);
int rightSize = countNodes(root.right);
return leftSize + rightSize + 1;
}
}
# 利用完全二叉树的性质
不过呢,我们上面两种方法,具有普适性,并没有利用好完全二叉树的性质。
完全二叉树只有两种情况
- 情况一:就是满二叉树
- 情况二:最后一层叶子节点没有满
对于情况一,可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为 1
对于情况二,分别递归左孩子,和右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后依然可以按照情况 1 直接用公式来计算。
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
TreeNode left = root.left;
TreeNode right = root.right;
int leftHeight = 0;
int rightHeight = 0;
while (left != null) {
left = left.left;
leftHeight ++;
}
while (right != null) {
// 注意这里,对于满二叉树/完全来说,非叶子节点的左子树总是不为空的
// 所以如果想要通过左右子树的高度来判断是否是满二叉树,对于右子树来说,必须遍历其右孩子而不是左孩子
right = right.right;
rightHeight ++;
}
if (leftHeight == rightHeight) {
// 2 << leftHieght = 2 * (2 ^ leftHeight) = 2 ^ (leftHeight + 1) - 1
// 整棵树的高度是 leftHeight + 1
return (2 << leftHeight) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
如果对位运算不熟悉的话,可以改成下面这样:
# 💥 复杂度分析
- 空间复杂度:三种方法的空间复杂度都是 O(LogN)
- 时间复杂度:递归和迭代法的时间复杂度 O(N),利用完全二叉树的性质的解法其时间复杂度是 O(LogN * LogN)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10