题解 | #判断是不是完全二叉树#

<?php

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */
function isCompleteTree( $root )
{
    if($root == null){
        return true;
    }
    $list = [];
    $list[] = $root;
    while(!empty($list)){
        $pop = array_shift($list);
        if($pop->left != null && $pop->right != null){
            $list[] = $pop->left;
            $list[] = $pop->right;
        }elseif($pop->left != null && $pop->right == null){
            $list[] = $pop->left;
            break;
        }elseif($pop->left == null && $pop->right != null){
            return false;
        }else{
            break;
        }
    }
    while(!empty($list)){
        $pop = array_shift($list);
        if($pop->left != null || $pop->right != null){
            return false;
        }
    }
    return true;
}

BFS遍历，分为两个阶段:

1. 阶段一：判断节点是不是有两个子节点，或者只有左节点。如果是，把子节点放入队列；如果只有右节点，直接返回false；如果两个子节点都没有，或者只有左节点，进入下个阶段
2. 阶段二：判断队列里剩下的节点是不是都没有子节点，如果有子节点，返回false