Count complete binary tree

algorithm

(Banner图片来自一喜欢摄影的同学：心碎乌托邦)

题目

Leetcode 222 : Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2th nodes inclusive at the last level h.

题解

对于此问题，稍加思考就会想到使用binary search的方法。

首先的一个想法是，先算出树的高度，然后再用二分的方法求出最后一层节点的数量， 从而就能够统计出有多少节点。然后当我写完提交AC后，高兴了两秒，然后看到算法 时间上跟最优的差距有点大。然后有修补了一下，再提交发现还是有质的差距。

然后在discuss发现了高手的解法，但是只有代码，没有解释，我在此记录一下我的理解过程。

首先，贴出代码 

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
int result,height,RTreeHeight;
TreeNode* visit,*p;

if (root==NULL) return 0;

p = visit = root;
height = 0;
for(;p;p = p -> left) height++;
result = 1;

while(--height)
{
    result <<= 1;

    RTreeHeight = 0;
    p = visit->right;
    for(;p;p = p -> left) RTreeHeight++;

    if (RTreeHeight < height) visit = visit->left;
    else
    {
        result |= 1;
        visit = visit->right;
    }
}
return result;

算法的过程就是每次计算右儿子的高度，如果右儿子的高度和树的高度一样就加1。

算法比较难理解的是result的计算方式，每次左移一位。如果理解后发现其实挺 巧妙的。

例子

binary tree 首先，这棵树高度为3，result初始为1，所以1<<3=8刚好等于树中节点的数量， 大家就可以发现这其中的巧妙了。

binary tree 然后，当再加几个node（红色）时，你又会发现4=1<<2。

所以，通过上面这两个图，我们可以总结出算法的思想。

  1. 首先，求出树的高度height，然后这部分节点的数量是1<<height;
  2. 然后，再利用二分的思想求出最底层的节点。