给出一个完全二叉树,求出该树的节点个数。
说明:
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 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 |
|