222. 完全二叉树的节点个数【 力扣(LeetCode) 】
文章目录
- 零、原题链接
- 一、题目描述
- 二、测试用例
- 三、解题思路
- 3.1 递归
- 3.2 二分搜索(非递归）
- 四、参考代码
- 4.1 递归
- 4.2 二分搜索
零、原题链接
222. 完全二叉树的节点个数
一、题目描述
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
二、测试用例
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树
三、解题思路
3.1 递归
- 基本思路：
一般是采用遍历所有节点的方法来计算节点个数，既然进阶说有非 O ( n ) \Omicron(n) O(n)的复杂度，那一般是利用满二叉树的性质；在满二叉树中，左右子树树高一样，则左子树为完全满二叉树，即节点数为 2 h − 1 2^{h}-1 2h−1；不一样，则右子树为完全满二叉树；所以可以利用这个性质，不断递归，计算子树节点数。 - 具体思路：
- 先计算左右子树树高；
- 相同，则返回 左子树节点数 + 递归计算右子树节点个数；
- 不同，则返回 递归计算左子树节点个数 + 右子树节点数；
3.2 二分搜索(非递归）
- 基本思路：
根据左右子树树高，不断缩小最后一行最后一个元素所在的位置的范围； - 具体思路：
- 先确定初始范围为： [ 0 , 2 ( h − 1 ) ] [0,2^{(h-1)}] [0,2(h−1)]
- 遍历子树：
- 左右子树树高相同，最后一个元素在右子树，修改范围下限；
- 不相同，在左子树，修改范围上限；
- 总节点数为：树高为 h-1 的完全二叉树的节点数 + 范围上限；
四、参考代码
4.1 递归
时间复杂度：
O
(
h
2
)
\Omicron(h^2)
O(h2)【不断计算子树的树高，即：
1
+
2
+
⋯
+
h
=
h
2
+
h
2
1+2+\dots+h=\frac{h^2+h}{2}
1+2+⋯+h=2h2+h】
空间复杂度：
O
(
h
2
)
\Omicron(h^2)
O(h2)【计算树高其实可以用循环解决，这样空间复杂度就只剩
O
(
h
)
\Omicron(h)
O(h)】
/**
* 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) {
if (!root)
return 0;
int lh = countH(root->left);
int rh = countH(root->right);
if (lh == rh)
return pow(2, lh) + countNodes(root->right);
else
return countNodes(root->left) + pow(2, rh);
}
int countH(TreeNode* root) {
if (!root)
return 0;
return countH(root->left) + 1;
}
};
4.2 二分搜索
时间复杂度：
O
(
h
2
)
\Omicron(h^2)
O(h2)【不断计算子树的树高，即：
1
+
2
+
⋯
+
h
=
h
2
+
h
2
1+2+\dots+h=\frac{h^2+h}{2}
1+2+⋯+h=2h2+h】
空间复杂度：
O
(
1
)
\Omicron(1)
O(1)
/**
* 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) {
if (!root)
return 0;
TreeNode* p = root;
int l = 0;
int r = pow(2, countH(p) - 1) - 1;
while (p->left) {
if (countH(p->left) == countH(p->right)) {
p = p->right;
l = (l + r) / 2;
} else {
p = p->left;
r = (l + r) / 2;
}
}
return pow(2, countH(root) - 1) + r;
}
int countH(TreeNode* root) {
int h = 0;
for (TreeNode* p = root; p; p = p->left) {
h++;
}
return h;
}
};