已知一棵完全二叉樹，求其節(jié)點(diǎn)的個(gè)數(shù)
要求：時(shí)間復(fù)雜度低于O(N)，N為這棵樹的節(jié)點(diǎn)個(gè)數(shù)

時(shí)間復(fù)雜度分析：在求節(jié)點(diǎn)個(gè)數(shù)的時(shí)候，每一層只遍歷一個(gè)節(jié)點(diǎn)。
首先遍歷頭節(jié)點(diǎn)這一層，看左邊界，發(fā)現(xiàn)到底了；然后遍歷頭節(jié)點(diǎn)的右子樹的左邊界，發(fā)現(xiàn)到底了，就不看左子樹了，因?yàn)樽笞訕湟欢ㄊ菨M二叉樹；如果右子樹的左邊界沒到底，就不看右子樹了，就去遍歷左子樹。所以每一層遍歷的節(jié)點(diǎn)個(gè)數(shù)只有一個(gè)，而整棵樹一共有O(logN)層，每一層都會(huì)遍歷一次右子樹的左邊界，開銷為O(logN)，所以算法的時(shí)間復(fù)雜度為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 當(dāng)前節(jié)點(diǎn)
     * @param level 節(jié)點(diǎn)所在的層數(shù)
     * @param h 整棵樹的深度
     * @return 以node為頭節(jié)點(diǎn)的整棵樹的節(jié)點(diǎn)數(shù)
     */
    public static int bs(Node node, int level, int h) {
        if (level == h) { //葉節(jié)點(diǎn)
            return 1;
        }
        if (mostLeftLevel(node.right, level + 1) == h) {
            // 1. 求出node的右子樹的最左的邊界所在的層，是否和整棵樹的深度相等
            // 2. 如果相等，左子樹就是滿的，且左子樹的節(jié)點(diǎn)個(gè)數(shù)為 2^(h-level)-1
            // 3. 再加一個(gè)頭節(jié)點(diǎn)node，總數(shù)就是：2^(h-level)
            // 4. 遞歸求出右子樹的節(jié)點(diǎn)個(gè)數(shù)
            // 5. 步驟3和4加起來就是以node為頭節(jié)點(diǎn)的樹的總節(jié)點(diǎn)個(gè)數(shù)
            return (1 << (h - level)) + bs(node.right, level + 1, h);
        } else {
            // 1. 右子樹的左邊界所在層數(shù)不等于整棵樹的深度
            // 2. 右子樹高度比左子樹少1,為 2^(h-level-1)-1
            // 3. 再加一個(gè)頭節(jié)點(diǎn)node，總數(shù)就是：2^(h-level-1)
            // 4. 遞歸求出左子樹的節(jié)點(diǎn)個(gè)數(shù)
            // 5. 步驟3和4加起來就是以node為頭節(jié)點(diǎn)的樹的總節(jié)點(diǎn)個(gè)數(shù)
            return (1 << (h - level - 1)) + bs(node.left, level + 1, h);
        }
    }

    /**
     * @param node 當(dāng)前節(jié)點(diǎn)
     * @param level 節(jié)點(diǎn)所在層數(shù)
     * @return 整棵樹最左的邊界所在的層數(shù)
     */
    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));

    }

}