二叉树的完全性检验

[Sunny-117]

No description provided.

[lxy-Jason]

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isCompleteTree = function(root) {
    const queue = [root];
    let leaf = false; //标记是否已经遇到过左右叶子不完整的节点
    while(queue.length){
        let len = queue.length;
        let node = queue.shift();
        if(!node.left && node.right){ //有右节点没左节点,肯定不是完全二叉树
            return false;
        }
        if(leaf && (node.left || node.right)){ // 如果已经遇到过左右节点不完整的节点了,还碰到不是叶子节点的节点,也不是完全二叉树
            return false;
        }
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
        if(!leaf && (!node.left || !node.right)){ //首次碰到左右不全的节点,leaf为true;
            leaf = true;
        }
    }
    return true;
};