【LeetCode每日一题】222.完全二叉树的节点个数.md

222.完全二叉树的节点个数

给出一个完全二叉树,求出该树的节点个数。
说明:
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例:
输入:

1
2
3
4
5
6
>     1
> / \
> 2 3
> / \ /
> 4 5 6
>

输出: 6

计算一棵二叉树有多少个节点,我们直接遍历整个树,便可得到结果。

但题目中给出的二叉树更特殊,是一棵完全二叉树,如果直接遍历整棵树,完全二叉树这个条件就没用到,所以,直接遍历计算,肯定不是最优解。

那我们怎么能够利用完全二叉树这个条件呢?

根据定义,完全二叉树是依次从上往下,从左往右的顺序填满二叉树,除了最底层可能没满,其余每层节点都满了。

而且,我们要计算的只是树的节点个数,不需要知道每个节点的值是多少。所以,我们其实只关系节点的位置即可,不需要关系节点值。

再观察这个完全二叉树。


一棵完全二叉树是按照入上图所示的顺序依次填满的。

这里节点的索引是顺序的。

再者,对于完全二叉树的每一层,最多有2^n个节点(这里我们把根节点当作第0层)。所以对于一个有n层的完全二叉树而言,第n层的节点顺序介于[2^n, 2^(n+1)-1]。
比如上面这个示例完全二叉树有2层,第2层(最底层)节点索引是[4,5,6],介于[4,7]之间。

所以这个题目,我们先计算一下二叉树有多少层,然后判断这一层节点索引最大的一个是多少即可。由于最后一层节点索引介于[2^n, 2^(n+1)-1]之间,在最后判断时,我们可以使用二分查找来判断。

怎么判断一个节点到底在不在呢?

我们将二叉树节点索引写成二进制表示:

我们发现,每一个节点的索引,写成二进制后,其对应的都是,从根节点到该节点的路径,根节点永远填1,往左填0,往右填1。
比如5个节点,索引二进制为 101,对应从根节点的路径是 根-左-右;再比如第4个节点,100,对应路径为根-左-左。这样我们判断某个节点存不存在时,就可以直接从根节点判断其二进制对应的路径存不存在即可。

这是一个非常巧妙的关系,是巧合么?
当然不是。
我们刚才说了,对于一个完全二叉树,节点是从上往下,从左往右的顺序依次填的。
根节点为第一个节点,永远为1对吧。
第二个节点是根节点的左子节点,其索引在根节点的索引上+1,二进制计算,1+1进1得0。
再到第三个节点,根节点右子节点,在第二个节点索引上+1,0+1得1。
第四个节点,第二个节点左子节点,在第三个节点索引上+1,1+1进1得0
第五个节点,第二个节点的右子节点,在第四个节点索引上+1,0+1得1

每个左子节点都是1+1进1得0,每个右子节点都是0+1得1

刚才说了,对于一个有n层的完全二叉树,第n层节点的索引值在区间[2^n, 2^(n+1)-1],我们可以使用二分查找的方式,查找该区间上存在于二叉树的最大索引值即可,判断方式就是上面这个,根据其二进制与其路径的判断。

整个算法复杂度为 O((logn)^2)。首先计算树的层数,需要O(logn)复杂度。然后对于每个节点的判断,都要O(logn)。

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

func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
level := 0
for node := root; node.Left != nil; node = node.Left {
level++
}
return sort.Search(1<<(level+1), func(k int) bool {
if k <= 1<<level {
return false
}
bits := 1 << (level - 1)
node := root
for node != nil && bits > 0 {
if bits&k == 0 {
node = node.Left
} else {
node = node.Right
}
bits >>= 1
}
return node == nil
}) - 1
}