判斷二叉樹是否為完全二叉樹

判斷二叉樹是否為完全二叉樹。完全二叉樹的定義是，前n-1層都是滿的，第n層如有空缺，則是缺在右邊，即第n層的最右邊的節點，它的左邊是滿的，右邊是空的。

這個問題的描述已經提示了解法，采用廣度優先遍歷，從根節點開始，入隊列，如果隊列不為空，循環。遇到第一個沒有左兒子或者右兒子的節點，設置標志位，如果之后再遇到有左/右兒子的節點，那么這不是一顆完全二叉樹。

這個方法需要遍歷整棵樹，復雜度為O(N)，N為節點的總數。

#include<iostream>
#include<queue>
using namespace std;
bool leftMost =false;
queue<Node*> q;
bool ProcessChild(Node* node)
{
	if(node)
	{
		if(!leftMost)
		{
			q.push_back(node);
		}
		else
			return false;
	}
	else
		leftMost=true;
	return true;
}
bool IsCompleteBinaryTree(Node* root)//層序遍歷 
{
	if(root==NULL)
		return true;
	q.push_back(root);
	while(!q.empty())
	{
		Node* node=q.pop();
		if (!ProcessChild(node->left))  
            return false;  
  
        //處理右節點  
        if (!ProcessChild(node->right))  
            return false;  
	}
	return true;

}