题目描述（中等难度）

给一个完全二叉树，输出它的节点个数。

解法之前

因为中文翻译的原因，对一些二叉树的概念大家可能不一致，这里我们统一一下。

• full binary tree

  下边是维基百科的定义。

  每个节点有 或 2 个子节点。

• perfect binary tree

  

  下边是维基百科的定义。

  A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.An example of a perfect binary tree is the (non-incestuous) ancestry chart of a person to a given depth, as each person has exactly two biological parents (one mother and one father). Provided the ancestry chart always displays the mother and the father on the same side for a given node, their sex can be seen as an analogy of left and right children, children being understood here as an algorithmic term. A perfect tree is therefore always complete but a complete tree is not necessarily perfect.

  除了叶子节点外，所有节点都有两个子节点，并且所有叶子节点拥有相同的高度。

此外，对于 perfect binary tree，总节点数就是一个等比数列相加。

第1层 1 个节点，第2层 2 个节点，第3层 4 个节点，…，第层

个节点。

相加的话，通过等比数列求和的公式。

这里的话，首项 a1 是 1，公比 q 是 2，项数 n 是 h，代入上边的公式，就可以得到节点总数是

。

解法一

首先我们考虑普通的二叉树，怎么求总结数。只需要一个递归即可。

接下来考虑优化，参考 。

上边不管当前是什么二叉树，就直接进入递归了。但如果当前二叉树是一个 perfect binary tree，我们完全可以用公式算出当前二叉树的总节点数。

上边用了位运算，1 << h1 等价于

，记得加上括号，因为 运算的优先级比加减还要低。

时间复杂度的话，分析主函数部分，主要是两部分相加。

假如 countNodes 的时间消耗是 T(n)。那么对于不是 perfect binary tree 的子树，时间消耗就是 T(n/2)，perfect binary tree 那部分因为计算了树的高度，就是 clog(n)。

所以时间复杂度就是 O(log²(n))。

解法二

参考 这里2)。

解法一中，我们注意到对于 complete binary tree ，左子树和右子树中一定存在 perfect binary tree，而 perfect binary tree 的总结点数可以通过公式计算。所以代码也可以按照下边的思路写。

通过判断整个树的高度和右子树的高度的关系，从而推断出左子树是 perfect binary tree 还是右子树是 perfect binary tree。

如果右子树的高度等于整个树的高度减 1，说明左边都填满了，所以左子树是 perfect binary tree ，如下图。

否则的话，右子树是 perfect binary tree ，如下图。

代码的话，因为是 complete binary tree，所以求高度的时候，可以一直向左遍历。

时间复杂度的话，因为使用了类似二分的思想，每次都去掉了二叉树一半的节点，所以总共会进行 O(log(n)) 次。每次求高度消耗 。因此总的时间复杂度也是 O(log²(n))。

总

解法一相对更容易想到。不过两种解法都抓住了一个本质，对于 complete binary tree ，左子树和右子树中一定存在 perfect binary tree 。根据这条规则实现了两个算法。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情