题目：统计完全二叉树节点个数。

观察完全二叉树的结构发现主要有如下几种：规律就是要么根节点的左子树为满二叉树，要么根节点的右子树为满二叉树。

思路： 首先，如果当前节点的右子树最左边那个节点和二叉树的层数（深度）一样则说明该节点的左子树为满二叉树，如上图左边所示，的确根节点的右子树的最左边那个节点所在层数和二叉树的层数是一样的，那么整颗二叉树的节点个数就是左边满二叉树的节点+当前节点(根节点)+递归右子树节点个数。反之，当前节点的右子树最左边那个节点没有到达二叉树的层数（深度），则就是上图右边的情况：该节点的右子树为一颗满二叉树。那么整颗二叉树的节点个数就是右边满二叉树的节点+当前节点(根节点)+递归左子树节点个数。

 实现代码：

//接受两个参数，节点指针和节点所在层数，最后返回最左侧节点所在层数
int mostLeftLevel(TreeNode* node, int level) {
	while (node != NULL) {
		level++;
		node = node->left;
	}
	return level - 1;
}
int nodeNum(TreeNode* root) {
	if (root == NULL)
		return 0;
	return bs(root, 1, mostLeftLevel(root, 1));//root为头结点，1位当前节点所在层数，mostLeftLevel求得是当前节点左侧的深度
}
int bs(TreeNode* node, int level, int h) {
	if (level == h)//如果当前层数等于总层数h则返回1表示只有一个节点
		return 1;
	if (mostLeftLevel(node->right, level + 1) == h) {//如果当前节点的右子树的最左边那个节点到达了最后一层位置，该节点的左子树必为一个满二叉树：
		//那么应该返回该节点的满二叉树即左子树的节点个数+当前节点+右子树递归
		return (1 << (h - level)) + bs(node->right, level + 1, h);
	}
	else {//如果当前节点的右子树的最左边那个节点还没有到达最后一层位置，那么该右子树必为满二叉树：
		//应该返回该满二叉树即右子树的节点个数+当前节点+左子树递归
		return(1 << h - level - 1) + bs(node->left,level + 1, h);

	}
}

测试二叉树为上图四种情况，测试代码如下：

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

class TreeNode{
public:
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int val){
		this->val = val;
		left = NULL;
		right = NULL;
	}
};
TreeNode* creatTreeNode()
{
	TreeNode *p;
	int data;
	cin >> data;
	if (data == -1)
		p = NULL;
	else
	{
		p = new TreeNode(data);
		p->left = creatTreeNode();
		p->right = creatTreeNode();
	}
	return p;
}
//接受两个参数，节点指针和节点所在层数，最后返回最左侧节点所在层数
int mostLeftLevel(TreeNode* node, int level) {
	while (node != NULL) {
		level++;
		node = node->left;
	}
	return level - 1;
}
int bs(TreeNode* node, int level, int h) {
	if (level == h)//如果当前层数等于总层数h则返回1表示只有一个节点
		return 1;
	if (mostLeftLevel(node->right, level + 1) == h) {//如果当前节点的右子树的最左边那个节点到达了最后一层位置，该节点的左子树必为一个满二叉树：
		//那么应该返回该节点的满二叉树即左子树的节点个数+当前节点+右子树递归
		return (1 << (h - level)) + bs(node->right, level + 1, h);
	}
	else {//如果当前节点的右子树的最左边那个节点还没有到达最后一层位置，那么该右子树必为满二叉树：
		//应该返回该满二叉树即右子树的节点个数+当前节点+左子树递归
		return(1 << (h - level - 1)) + bs(node->left, level + 1, h);

	}
}
int nodeNum(TreeNode* root) {
	if (root == NULL)
		return 0;
 	return bs(root, 1, mostLeftLevel(root, 1));//root为头结点，1位当前节点所在层数，mostLeftLevel求得是当前节点左侧的深度
}
int main(){
	while (cin) {
		TreeNode* p = creatTreeNode();
		int number = nodeNum(p);
		cout << number << endl;
	}
}

 测试结果：