（三十一）判断一个树是否是完全二叉树

【完全二叉树】

• 定义
  • 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树
    
• 特点
  • 叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树
• 性质
  • [1] 具有n个结点的完全二叉树的深度（注：[ ]表示向下取整）
  • [2] 如果对一棵有n个结点的完全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n) 有:
    • 如果i=1, 则结点i是二叉树的根, 无双亲;如果i>1, 则其双亲parent (i) 是结点[i/2].
    • 如果2i>n, 则结点i无左孩子, 否则其左孩子lchild (i) 是结点2i;
    • 如果2i+1>n, 则结点i无右孩子, 否则其右孩子rchild (i) 是结点2i+1.

【解题思路】

• 层序遍历二叉树，如果当前节点有右节点，但是没有左节点，则直接返回false；
• 如果当前节点并不是左右节点都有，那么之后的节点必须都为叶节点，否则返回false;

【C++代码】

bool isCBT(TreeNode* node){
    if(node == NULL)
        return true;
    queue que;
    bool leaf = false;
    TreeNode *cur = node,*l = NULL,*r = NULL;
    que.push(cur);

    while(!que.empty()){
        cur = que.front();
        que.pop();
        l = cur->left;
        r = cur->right;
        
        if((leaf && (l != NULL || r != NULL)) || (l == NULL && r != NULL)){
            return false;
        }
        if(l != NULL)
            que.push(l);
        if(r != NULL){
            que.push(r);
        }else{
            leaf = true;
        }
    }
    return true;
}