判斷二叉樹是否為完全二叉樹。完全二叉樹的定義是，前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;
}