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

要求：时间复杂度低于O(N)，N为这棵树的节点个数
思想：如果采用遍历的话，那么复杂度就刚好是O(n)。不符合要求；
首先我们可以知道对于一个完全二叉树来说，具有n个节点的完全二叉树的深度是（log以2为底n）+1，所有我们可以先得到这棵二叉树的深度，即一共有多少层。然后判断这棵二叉树的右子树是否也到达了这个深度，如果到了，那么这棵二叉树的左子树一定是一棵满二叉树。再依次使用递归判断右子树。如果右子树没有到达那个深度，那么右子树一定是一棵满二叉树，便可以得到右子树的节点数是多少，再通过递归依次判断右子树。一棵满二叉树的结点个数是2的K次方-1。
代码：

public class Count{

	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 level, int h) {
		if (level == h) {
			return 1;
		}
		if (mostLeftLevel(node.right, level + 1) == h) { //如果右子树到达了二叉树的底部，那么左子树的节点数就可以算出来
			return (1 << (h - l)) + bs(node.right, level + 1, h); //1 << (h - l))的意思是2的h-1次方
		} else { //如果右子树没有到，那么右子树一定是一个满二叉树，可以算出来右子树的节点数*
			return (1 << (h - l - 1)) + bs(node.left, level + 1, h);
		}
	}

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

	}

}

这个算法的复杂度是O(log以2为底n)的平方。