已知一棵完全二叉树，求其节点的个数

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

时间复杂度分析：在求节点个数的时候，每一层只遍历一个节点。
首先遍历头节点这一层，看左边界，发现到底了；然后遍历头节点的右子树的左边界，发现到底了，就不看左子树了，因为左子树一定是满二叉树；如果右子树的左边界没到底，就不看右子树了，就去遍历左子树。所以每一层遍历的节点个数只有一个，而整棵树一共有O(logN)层，每一层都会遍历一次右子树的左边界，开销为O(logN)，所以算法的时间复杂度为O((logN)^2)。

public class CompleteTreeNodeNumber {

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

        public Node(int data) {
            this.value = data;
        }
    }

    public static int nodeNum(Node head) {
        if (head == null) {
            return 0;
        }
        return bs(head, 1, mostLeftLevel(head, 1));
    }

    /**
     * @param node 当前节点
     * @param level 节点所在的层数
     * @param h 整棵树的深度
     * @return 以node为头节点的整棵树的节点数
     */
    public static int bs(Node node, int level, int h) {
        if (level == h) { //叶节点
            return 1;
        }
        if (mostLeftLevel(node.right, level + 1) == h) {
            // 1. 求出node的右子树的最左的边界所在的层，是否和整棵树的深度相等
            // 2. 如果相等，左子树就是满的，且左子树的节点个数为 2^(h-level)-1
            // 3. 再加一个头节点node，总数就是：2^(h-level)
            // 4. 递归求出右子树的节点个数
            // 5. 步骤3和4加起来就是以node为头节点的树的总节点个数
            return (1 << (h - level)) + bs(node.right, level + 1, h);
        } else {
            // 1. 右子树的左边界所在层数不等于整棵树的深度
            // 2. 右子树高度比左子树少1,为 2^(h-level-1)-1
            // 3. 再加一个头节点node，总数就是：2^(h-level-1)
            // 4. 递归求出左子树的节点个数
            // 5. 步骤3和4加起来就是以node为头节点的树的总节点个数
            return (1 << (h - level - 1)) + bs(node.left, level + 1, h);
        }
    }

    /**
     * @param node 当前节点
     * @param level 节点所在层数
     * @return 整棵树最左的边界所在的层数
     */
    public static int mostLeftLevel(Node node, int level) {
        while (node != null) {
            level++;
            node = node.left;
        }
        return level - 1;
    }

    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(nodeNum(head));

    }

}