拓展：如何计算完全二叉树的节点数
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 222. Count Complete Tree Nodes | 🟠 |
Prerequisite Knowledge
Before reading this article, you need to first learn:
If you're asked to count the number of nodes in a regular binary tree, it's simple. You just need to add some code to the binary tree traversal framework.
However, in LeetCode Problem 222 "Count Complete Tree Nodes," you are given a complete binary tree and asked to count its nodes. Can you do it? What is the algorithm's time complexity?
The time complexity of this algorithm should be O(logN*logN). If the algorithm in your mind is not this efficient, then this article is for you.
For definitions of terms like "complete binary tree" and "full binary tree," you can refer to the basic knowledge section Binary Tree Basics.
1. Analysis of the Approach
Now let's get back to the main topic. How do we count the number of nodes in a complete binary tree?
// input a complete binary tree, return the total number of nodes
int countNodes(TreeNode root);// input a complete binary tree, return the total number of nodes
int countNodes(TreeNode* root);# Input a complete binary tree, return the total number of nodes
def countNodes(root: TreeNode) -> int:// Given a complete binary tree, return the total number of nodes
func countNodes(root *TreeNode) int {
}// Given a complete binary tree, return the total number of nodes
var countNodes = function(root) {}If it is a regular binary tree, you can simply traverse it as follows, with a time complexity of O(N):
public int countNodes(TreeNode root) {
if (root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}def countNodes(root: TreeNode) -> int:
if root == None:
return 0
return 1 + countNodes(root.left) + countNodes(root.right)func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + countNodes(root.Left) + countNodes(root.Right)
}var countNodes = function(root) {
if (root === null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
};If it is a full binary tree, the total number of nodes grows exponentially with the height of the tree:
public int countNodes(TreeNode root) {
int h = 0;
// calculate the height of the tree
while (root != null) {
root = root.left;
h++;
}
// the total number of nodes is 2^h - 1
return (int)Math.pow(2, h) - 1;
}int countNodes(TreeNode* root) {
int h = 0;
// calculate the height of the tree
while (root != nullptr) {
root = root->left;
h++;
}
// the total number of nodes is 2^h - 1
return pow(2, h) - 1;
}def countNodes(root: TreeNode) -> int:
h = 0
# Calculate the height of the tree
while root:
root = root.left
h += 1
# The total number of nodes is 2^h - 1
return 2 ** h - 1func countNodes(root *TreeNode) int {
h := 0
// calculate the height of the tree
for root != nil {
root = root.Left
h++
}
// the total number of nodes is 2^h - 1
return int(math.Pow(2, float64(h))) - 1
}var countNodes = function(root) {
var h = 0;
// Calculate the height of the tree
while (root !== null) {
root = root.left;
h++;
}
// The total number of nodes is 2^h - 1
return Math.pow(2, h) - 1;
};A complete binary tree is more special than a regular binary tree but not as special as a full binary tree. Calculating the total number of its nodes can be seen as a combination of the methods used for regular and complete binary trees. Let's look at the code first:
class Solution {
public int countNodes(TreeNode root) {
TreeNode l = root, r = root;
// Calculate the height along the leftmost and rightmost sides respectively
int hl = 0, hr = 0;
while (l != null) {
l = l.left;
hl++;
}
while (r != null) {
r = r.right;
hr++;
}
// If the heights calculated on the left and right sides are the same, it's a full binary tree
if (hl == hr) {
return (int)Math.pow(2, hl) - 1;
}
// If the heights of the left and right sides are different, calculate using the logic for a regular binary tree
return 1 + countNodes(root.left) + countNodes(root.right);
}
}class Solution {
public:
int countNodes(TreeNode* root) {
TreeNode* l = root, * r = root;
// Calculate the height along the leftmost and rightmost sides respectively
int hl = 0, hr = 0;
while (l != nullptr) {
l = l->left;
hl++;
}
while (r != nullptr) {
r = r->right;
hr++;
}
// If the heights calculated on the left and right sides are the same, it's a full binary tree
if (hl == hr) {
return pow(2, hl) - 1;
}
// If the heights of the left and right sides are different, calculate using the logic for a regular binary tree
return 1 + countNodes(root->left) + countNodes(root->right);
}
};class Solution:
def countNodes(self, root: TreeNode) -> int:
l = root
r = root
hl = 0
hr = 0
# calculate the height along the leftmost and rightmost sides respectively
while l is not None:
l = l.left
hl += 1
while r is not None:
r = r.right
hr += 1
# if the heights calculated on the left and right sides are the same, it's a full binary tree
if hl == hr:
return pow(2, hl) - 1
# if the heights of the left and right sides are different, calculate using the logic for a regular binary tree
return 1 + self.countNodes(root.left) + self.countNodes(root.right)func countNodes(root *TreeNode) int {
l, r := root, root
// Calculate the height along the leftmost and rightmost sides respectively
hl, hr := 0, 0
for l != nil {
l = l.Left
hl++
}
for r != nil {
r = r.Right
hr++
}
// If the heights calculated on the left and right sides are the same, it's a full binary tree
if hl == hr {
return int(math.Pow(2, float64(hl))) - 1
}
// If the heights of the left and right sides are different, calculate using the logic for a regular binary tree
return 1 + countNodes(root.Left) + countNodes(root.Right)
}var countNodes = function(root) {
let l = root, r = root;
// calculate the height along the leftmost and rightmost sides respectively
let hl = 0, hr = 0;
while (l !== null) {
l = l.left;
hl++;
}
while (r !== null) {
r = r.right;
hr++;
}
// if the heights calculated on the left and right sides are the same, it's a full binary tree
if (hl === hr) {
return Math.pow(2, hl) - 1;
}
// if the heights of the left and right sides are different, calculate using the logic for a regular binary tree
return 1 + countNodes(root.left) + countNodes(root.right);
};Combining the algorithms for full binary trees and regular binary trees discussed earlier, the above code should be easy to understand—it is a combined version. However, the technique to reduce the time complexity is very subtle.
2. Complexity Analysis
As mentioned at the beginning, the time complexity of this algorithm is O(logN * logN). How is this calculated?
Intuitively, you might think the worst-case scenario is O(N * logN), because the previous while loop takes logN time, and then it takes O(N) time to recurse into the left and right subtrees:
return 1 + countNodes(root.left) + countNodes(root.right);The key point is that only one of the two recursions will actually continue, while the other will trigger hl == hr and return immediately without further recursion.
Why is this? Here’s the reason:
In a complete binary tree, at least one of its subtrees is a full binary tree:
As shown in the picture, due to the properties of a complete binary tree, one of its subtrees must be full. This ensures that hl == hr will be triggered, consuming only O(logN) complexity without continuing the recursion.
In summary, the recursion depth of the algorithm is the height of the tree, which is O(logN). The time spent on each recursion is the while loop, which requires O(logN). Therefore, the overall time complexity is O(logN*logN).
So, the concept of a "complete binary tree" exists for a reason. It is not only useful for implementing binary heaps using arrays but also for efficiently computing the total number of nodes, which might seem like a simple operation.
