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

已知一棵完全二叉树，求其节点的个数
要求：时间复杂度低于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));

	}

}