【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
}