判断二叉树是否为完全二叉树-创新互联

判断二叉树是否为完全二叉树。完全二叉树的定义是，前n-1层都是满的，第n层如有空缺，则是缺在右边，即第n层的最右边的节点，它的左边是满的，右边是空的。

这个问题的描述已经提示了解法，采用广度优先遍历，从根节点开始，入队列，如果队列不为空，循环。遇到第一个没有左儿子或者右儿子的节点，设置标志位，如果之后再遇到有左/右儿子的节点，那么这不是一颗完全二叉树。

这个方法需要遍历整棵树，复杂度为O(N)，N为节点的总数。

#include
#include
using namespace std;
bool leftMost =false;
queue 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;

}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。