求完全二叉树节点的个数时间复杂度不能大于O(n)

首先知道一个公式：

如果一棵二叉树为满二叉树，那么该满二叉树的节点个数为(2^h)-1，其中h为该满二叉树的高度。

我们利用这一个公式来实现求完全二叉树的节点的个数，并且时间复杂度不大于O(n)。

算法原理：

通过寻找整棵二叉树的满二叉子树，找到后直接运用公式求该满二叉子树的节点个数。这样就省去了遍历二叉树的时间，使算法的时间复杂度降低。

算法流程：

我们以下图为例讲：

                                                        图一

 

                                                        图二

1：先求出整棵二叉树的层数h，上图一中h等于4。

2：然后求出这个二叉树的右子树最左的节点所在的层数

3：如果右子树最左的节点所在的层数等于整棵二叉树的层数，上图一，那么这个二叉树的左子树就是一个满二叉树，运用公式求出其节点个数，然后加上1号节点。

4：剩下的就是整个二叉树的右子树，还是一个完全二叉树，递归求解

上面是图一版本，下面讲一下图二版本的算法流程

1：先求出整棵二叉树的层数h，上图二中h等于4。

2：然后求出这个二叉树的右子树最左的节点到了整个二叉树的哪一层。

3：如果右子树最左的节点所在的层数不等于整棵二叉树的层数，上图二，那么这个二叉树的右子树就是一个满二叉树，运用公式求出其节点个数，然后加上1号节点。

4：剩下的就是整个二叉树的左子树，还是一个完全二叉树，递归求解。

代码实现：

​ struct node { node left; node right; int value; }; int mostleftlevel (int level,node head)//这个函数求的是以head为头节点的二叉树的层数是多少。level代表head节点在整棵二叉树中的第几层 { while (head!=null)//只要head不等于空，说明还可以往下走 { level++;//层数＋1 head=head.left;//往二叉树的下面走 } return level-1;//最后算出来多一个，减去 } int bs(int level,node head,int h)//这个函数求的是以head为头节点的完全二叉树的节点的个数。level代表head节点在整棵二叉树中的层数，h为整棵二叉树的层数，在整个函数运行中一直保持不变 { if(level==h)//这个条件满足，说明head节点为叶节点，节点个数为1 return 1; if(mostleftlevel(level+1,head.right)==h)//判断条件前面的函数调用求的是这个二叉树的右子树最左的节点所在的层数，如果等于整个二叉树的层数，说明左子树为满二叉树 return (2<<(h-level))-1+bs(level+1,head.right,h);//通过公式求解左子树的节点个数，递归继续求右子树的节点个数 else //如果不等于整个二叉树的层数，说明右子树为满二叉树 return (2<<(h-level-1))-1+bs(level+1,head.left,h);//通过公式求解右子树的节点个数，递归求左子树的节点个数 } int nodenum(node head)//主函数 { return bs(1,head,mostleftlevel(1,head)); } ​

接下来分析一下这个程序的时间复杂度：

 

以上图为例，分析程序如何访问二叉树中的点。首先ds函数访问1号顶点，此时右子树最左的节点所在的层数等于整个二叉树的层数----->递归访问3号节点，此时右子树最左的节点(7号)所在的层数不等于整个二叉树的层数----->递归访问6号节点，此时右子树最左的节点(6号)所在的层数不等于整个二叉树的层数----->递归访问12号节点，到达叶子节点了，返回1。

通过上面的分析可得，递归函数df访问节点的顺序为1--->3--->6--->12，可以得到，递归函数只访问一层中的一个节点，那么时间复杂度为O（log n），但每次访问节点时都得求出其右子树最左的节点所在的层数，这个过程的时间复杂度

也为O（log n），所以，总的时间复杂度为O（（log n）^2）--->递归的整个过程的时间复杂度为O(log n)，而每次重新进入一个递归函数时会发生mostleftlevel这个函数，这个函数的时间复杂度也为O(log n)，相当于一个for循环中又套了一个for循环，时间复杂度为O（（log n）^2）。