完全二叉树节点个数，时间复杂度O(N)以内_完全二叉树的时间复杂度

题目要求

给定一颗完全二叉树，请求出该完全二叉树节点个数。要求时间复杂度在O(N)以内。N为节点个数。

思路分析

求二叉树节点个数，第一反应就是常规遍历了，但是题目要求必须O(N)以内，再加上给的是完全二叉树。因此，此题肯定要利用完全二叉树的性质，来简化。
第一步，分析完全二叉树的性质：
1.只可能最后一行是不满的。
2.最后一行都是先从左边开始排列。
因此，此题的思路：
首先，先求出整棵树的最大深度。就是从根节点，依次遍历左孩子。
然后，从根节点右孩子开始，再次计算右孩子子树的最大深度。
此时，计算右孩子子树的最大深度加1，是否等于根节点的最大深度？
这一步计算是什么意思呢？其实就是在看，之前的完全二叉树，最后一行的节点数，是否过半。
为什么要看最后一行是否过半呢？那是因为
1.如果过半了，也就是右孩子子树的最大深度加1，等于根节点的最大深度。此时说明一个问题，根节点的左孩子子树，其实是一颗满二叉树。 此时直接利用满二叉树的性质：2的n次方-1，直接求出来左孩子子树的节点个数。
2.如果没过半，也说明一个问题，根节点的右孩子子树，其实是一个满二叉树。只不过，此时右孩子子树的满二叉树的高度，是深度-2，左孩子子树是满二叉树时，是深度-1。
当把两个子树中的其中一个子树，按照满二叉树的规则算出后，其实剩下的另一半子树，又是一颗完全二叉树，此时，其实就是把原问题变小了，看到把原来的问题，划分成相同的小问题时，想到了什么？对嘛，递归嘛，依次递归，问题就解决了。

代码

        public static int nodeNum(TreeNode node){
            if(node==null){
                return 0;
            }
            return bs(node,1,getDeep(node));
        }
        //递归
        public static int bs(TreeNode node,int now,int deep){
            if(now==deep){
                return 1;
            }
            if(getDeep(node.right)+now==deep){
                return (1<<(deep-now))+bs(node.right,now+1,deep);
            }else {
                return (1<<(deep-now-1))+bs(node.left,now+1,deep);
            }
        }
        //获取深度
        public static int getDeep(TreeNode node){
            int num=0;
            while (node!=null){
                num++;
                node=node.left;
            }
            return num;
        }
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

时间复杂度

此题目要求是，时间复杂度O(N)以内，那么此算法的时间复杂度，来分析一下。
首先，每递归到一个节点，都要计算深度，二叉树深度计算，O(logN）。
其次，每一层，其实只需要看一个节点，你看右孩子子树的高度时，就不需要看左孩子了。然后，直接排除掉一半孩子后，其实递归到下一层时，就剩一个节点了，因为另外一半排除掉了。因此，其实下一层，还是只看了一个节点，那也就是说，每一层都只看了一个节点。
那么，结合上面分析的，每一层只看一个节点，一共多少层？logN层。看每一个节点时，又要计算深度，logN。
那么，总时间复杂度，就是logN乘以logN。O(logN的平方)