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

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

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



#include<iostream>#include<queue>usingnamespacestd;boolleftMost=false;queue<Node*>q;boolProcessChild(Node*node){if(node){if(!leftMost){q.push_back(node);}elsereturnfalse;}elseleftMost=true;returntrue;}boolIsCompleteBinaryTree(Node*root)//层序遍历{if(root==NULL)returntrue;q.push_back(root);while(!q.empty()){Node*node=q.pop();if(!ProcessChild(node->left))returnfalse;//处理右节点if(!ProcessChild(node->right))returnfalse;}returntrue;}