给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:
1
2
3
4
5
6
7
8
| 输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6
|
方法一：暴力
:) 年轻人不讲码德，暴力就完事了。
1
2
3
4
5
6
7
8
9
| class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
|
方法二：二分查找 + 位运算
规定根节点位于第 0 层，完全二叉树的最大层数为 h。根据二叉树的性质，最后一层的结点数最少为 1，最多为 2^h。对于最大层数为 h 的完全二叉树，结点个数在 [2^h, 2^(h + 1) - 1]范围内，可以在该范围内使用二分查找来得到完全二叉树的结点个数。
根据结点个数范围的上下界得到当前需要判断的结点个数 k，如果第 k 个结点存在，则结点个数一定 大于等于 k，如果第 k 个结点不存在，则结点个数一定小于 k，因此可以将查找的范围缩小一半。
如何判断第 k 个结点是否存在，如果第 k 个结点位于第 h 层，则 k 的二进制表示包含 h + 1 位，其中最高位为 1，其余各位从高到低表示根节点到第 k 个结点的路径 ，0 表示移动到左子结点，1表示移动到右子结点。
例如数字 12 二进制表示 1100，则从根节点开始向下判断 右，左，左结点是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
int level = 0;
TreeNode node = root;
while(node.left != null){
++level;
node = node.left;
}
int low = 1 << level, high = (1 << (level + 1)) - 1;
while(low < high){
int mid = low +(high - low + 1) / 2;
if(exists(root, level, mid)){
low = mid;
}else{
high = mid - 1;
}
}
return low;
}
public boolean exists(TreeNode root, int level, int k){
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;
}
}
|
