求完全二叉树的节点个数

已知一棵完全二叉树，求其节点的个数
要求：时间复杂度低于O(N)，N为这棵树的节点个数

因为是完全二叉树，除了最后一层都是填满的，因此我们可以利用这个性质。
首先求出这个二叉树最大的高度，然后求其右子树的最大高度，如果两者是相等的，就说明左边是填满的，我们可以直接计算数量，否则的话就说明右面的最大高度是h - 1，同时在h - 1层右子树的高度也是填满的。
然后就进行递归来做。

package Code04;

public class Code08_NodeNumber {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        System.out.println(number(head));
    }


    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }
    public static int number(Node head){
        if(head == null) return 0;
        return bs(head, 1, mostLeftLevel(head, 1));
    }
    public static int bs(Node head, int level, int h){
        if(level == h) return 1;
        if(mostLeftLevel(head.right, level + 1) == h){
            return (1 << (h - level)) + bs(head.right, level + 1, h);
        }else{
            return (1 << (h - level - 1) + bs(head.left,level + 1, h));
        }
    }

    public static int mostLeftLevel(Node head, int level){
        if(head != null){
            level ++;
            head =head.left;
        }
        return level;
    }
}