222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root
,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h
层,则该层包含
1
∼
2
h
1 \sim 2^h
1∼2h 个节点。
示例 1:
输入: root = [1,2,3,4,5,6]
输出: 6
示例 2:
输入: root = []
输出: 0
示例 3:
输入: root = [1]
输出: 1
提示:
- 树中节点的数目范围是 [ 0 , 5 × 1 0 4 ] [0, 5 \times 10^4] [0,5×104]
- 0 ≤ N o d e . v a l ≤ 5 ∗ 104 0 \leq Node.val \leq 5 * 104 0≤Node.val≤5∗104
- 题目数据保证输入的树是 完全二叉树
进阶: 遍历树来统计节点是一种时间复杂度为 O(n)
的简单解决方案。你可以设计一个更快的算法吗?
解法一(统一迭代遍历)
思路分析:
-
采用统一迭代二叉树的遍历方法,来对二叉树进行遍历,在遍历的过程中统计节点数目
-
此处采用 前序遍历
实现代码如下:
class Solution {
public int countNodes(TreeNode root) {
int ans = 0;
if (root == null)
return ans; // 边界条件
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
// 对节点进行处理 添加待遍历节点
if (node.right != null)
stack.push(node.right);
if (node.left != null)
stack.push(node.left);
// 添加待处理节点
stack.push(node);
stack.push(null); // 使用null标记待处理节点
} else {
stack.pop(); // 弹出待处理节点
++ ans; // 对节点进行计数
}
}
return ans;
}
}
return ans;
}
}
提交结果如下:
解答成功:
执行耗时:9 ms,击败了5.25% 的Java用户
内存消耗:44.5 MB,击败了83.97% 的Java用户
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)
解法二(BFS+队列)
思路分析:
- 采用层序遍历法,对二叉树进行遍历,并在遍历过程中 统计节点数
实现代码如下:
class Solution {
// BFS
public int countNodes(TreeNode root) {
int ans = 0;
if (root == null)
return ans; // 边界条件
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; ++i) {
++ ans;
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return ans;
}
}
提交结果如下:
解答成功:
执行耗时:5 ms,击败了9.04% 的Java用户
内存消耗:46.5 MB,击败了5.07% 的Java用户
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)
解法三(二分查找+位运算)
思路分析:
-
首先题目给出该二叉树为 完全二叉树,因此可以利用完全二叉树的特性计算节点个数。
-
首先规定根节点位于第
0
层,完全二叉树的最大层数为h
,且根据完全二叉树的特性有;最左边的节点一定位于最底层,且从根节点到最左边的节点的路径长度即为最大层数h
-
当 0 ≤ i < h 0 \leq i < h 0≤i<h时,第
i
层包含 2 i 2^i 2i个节点,最底层包含节点数最少为1
,最多为 2 h 2^h 2h-
当底层包含
1
个节点时,完全二叉树的节点个数是: ∑ i = 0 h − 1 2 i + 1 = 2 h \sum_{i=0}^{h-1}2^i+1 = 2^h ∑i=0h−12i+1=2h -
当底层包含 2 h 2^h 2h个节点时,完全二叉树的节点个数时: ∑ i = 0 h = 2 h + 1 − 1 \sum_{i=0}^{h} = 2^{h+1} - 1 ∑i=0h=2h+1−1
-
-
因此对于最大层数为
h
的完全二叉树,节点个数在 [ 2 h , 2 h + 1 − 1 ] [2^h, 2^{h+1}-1] [2h,2h+1−1]的范围内,即在该范围内通过二分查找的方式得到完全二叉树的节点个数 -
即根据节点个数范围的上下界得到判断的节点个数
k
,如果第k
个节点存在,则节点个数一定大于或等于k
,如果第k
个节点不存在,则节点个数一定小于k
,因此每次查找的范围缩小一半,直到找到节点个数。 -
如何判断第
k
个节点是否存在?如果第k
个节点位于第h
层,则k
的二进制表示包含h+1
位,且最高位为1
,其余各位从高到底表示从根节点到第k
个节点的路径,0
表示移动到左子节点,1
表示移动到右子节点 -
通过位运算得到第
k
个节点对应的路径,然后判断该路径对应的节点是否存在,则可判断第k
个节点是否存在
实现代码如下:
class Solution {
// 二分查找 + 位运算
public int countNodes(TreeNode root) {
if (root == null) return 0; // 边界
// 获取二叉树的层数
int h = 0;
TreeNode node = root;
while (node.left != null) {
++ h; // 计算二叉树的层数
node = node.left;
}
// 根据二叉树的层数 获取节点数范围
int min = 1 << h; // 位运算计算 最低限度
int max = (1 << (h + 1)) - 1; // 位运算计算 最高限度
int ans = 0; // 即二分查找寻找符合条件的 用ans来保存
// 二分查找区间为 左闭右闭
while (min <= max) {
int mid = ((max - min) >> 1) + min;
if (exitTreeNode(mid, root, h)) {
// 如果存在 则继续查找
ans = mid;
min = mid + 1;
} else {
max = mid - 1;
}
}
return ans; // 在结束二分查找时 min指向的节点是最后一个存在的节点
}
private boolean exitTreeNode(int k, TreeNode root, int level) {
// 获取当前从根节点出发的方向
int bits = 1 << (level-1);
TreeNode node = root;
while (node != null && bits > 0) {
if ((bits & k) == 0) {
node = node.left;
} else {
node = node.right;
}
bits >>= 1;
}
return node != null;
}
}
提交结果如下:
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:46.4 MB,击败了8.84% 的Java用户
复杂度分析:
- 时间复杂度:
O
(
l
o
g
2
n
)
O(log^{2}_{}{n})
O(log2n),
n
为完全二叉树的节点数 - 空间复杂度: O ( 1 ) O(1) O(1),只使用有限的额外空间