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

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

思路：因为
$满树的节点数 =2^h-1$满树的节点数=2h−1
如果一个节点的右子树的最左节点到达完全二叉树的最后一层，则左子树为满树，节点个数等于左子树的节点数+递归求右子树的节点数+本节点，如果此节点的右子树的最左节点没有到完全二叉树的最后一层，则右子树为满树，节点个数等于右子树的节点数+递归求左子树的节点+本节点。

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));
	}

	public static int bs(Node node, int l, int h) {
		if (l == h) {
			return 1;
		}
		if (mostLeftLevel(node.right, l + 1) == h) {
			return (1 << (h - l)) + bs(node.right, l + 1, h);
		} else {
			return (1 << (h - l - 1)) + bs(node.left, l + 1, h);
		}
	}

	public static int mostLeftLevel(Node node, int level) {
		while (node != null) {
			level++;
			node = node.left;
		}
		return level - 1;
	}
}