统计完全二叉树的节点数

【题目】

给定一棵完全二叉树的头节点head，返回这棵树的节点个数。

【要求】

如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。

算法思路：在进入递归之前，先统计整个二叉树的高度h，然后看head节点的右子树的最左节点的高度（h1）与h的关系：

（1）如果head的右子树的最左节点h1到达二叉树的底部（h1==h），说明head节点的左子树是一颗满二叉树，返回整个左子树加head节点的数目+递归head节点的右子树；

（2）如果

head的右子树的最左节点h1未到达二叉树的底部（h1<h),此时head的左子树并不是满二叉树，说明head节点的右子树除去最后一层和head所在的顶层是一颗满二叉树，返回右子树（满二叉树）加head节点的数目+递归head节点左子树；

（3）如果当前节点所在的层数和完全二叉树的高度h一致，那么返回1；

用这种思路得到的算法复杂度为O(h^2);完全二叉树的每一层都有一个节点进入递归，每次递归都要求当前节点到右子树的最左节点的高度。

算法主要是用递归来对每一层的一个节点进行遍历，每次找到一个节点下面满二叉树（子树）+当前节点的数目，在遍历当前节点的左孩子或者右孩子。

最好画图进行观察

高度为h的满二叉树的节点数目为2^h-1.

主要代码如下：

public class Shu01 {	/**	 * 	 * @param head	 * @return	 * 题目：给定一棵完全二叉树的头节点head，返回这棵树的节点个数。	 *	【要求】	 *	如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。	 *	 */	public int nodeNum(Node head) {		if (head == null) {			return 0;		}		return bs(head, 1, mostLeftLevel(head, 1));	}	/**	 * 	 * @param node 表示任意一个节点	 * @param L	表示当前节点所在的层数（从1开始）	 * @param h	表示当前二叉树的高度	 * @return 通过递归返回的是二叉树的结点数目	 * 	 */	public 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);		}	}	/**	 * 	 * @param node 任意结点	 * @param level	当前节点所在的层数	 * @return 返回当前节点最左孩子所在的结点高度	 */	public int mostLeftLevel(Node node, int level) {		while (node != null) {			level++;			node = node.left;		}		return level - 1;	}	public static void main(String[] args) {		// TODO Auto-generated method stub	}}