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

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */
function isCompleteTree(root) {
    // write code here
    // 层序遍历函数
    function levelOrder(node) {
        if (node == null) {
            return true;
        }
        // 定义遍历的节点队列
        let query = [];
        query.push(node);
        let flag = false;
        while (query.length) {
            // 取出队列第一个节点
            let cur = query[0];
            // 弹出第一个节点
            query = query.slice(1);
            // console.log("cur:", cur);
            // 当第一次遇到空节点，则打标记
            if (cur == null) {
                flag = true;
                continue;
            }
            // 若第二次遇到空节点，则返回false
            // 完全二叉树若存在子节点，必须有左节点，若左节点为空，右节点非空则非完全二叉树
            if (flag) {
                return false;
            }
            // 向队列中添加左节点
            query.push(cur.left);
            // 向队列中添加右节点
            query.push(cur.right);
        }
        return true;
    }
    return levelOrder(root);
}
module.exports = {
    isCompleteTree: isCompleteTree,
};