20220519

完全二叉树

输入：{1,2,3,4,5,#,6}
返回值：false
说明：完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，
其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。
（第 h 层可能包含 [1~2h] 个节点）

解题思路：
因为完全二叉树有以下特点：
1. 除了最后一层，其他层没有空节点
2. 最后一层的节点必须集中在左侧
故逐层判断的逻辑如下：
1. 当存在右子树，却无左子树，说明当前层为不完全二叉树；
2. 当前面的节点缺少子节点，后面的节点不缺少子节点，说明当前层为不完全二叉树；
3.当下一层队列长度不为0时，说明并非最后一层，计算当前层队列长度，
  若满足len == 2**(depth-1)，说明当前层为满二叉树；
  若满足len != 2**(depth-1)，说明当前层为不完全二叉树；

function isCompleteTree( root ) {
    // write code here
    // 使用广度优先遍历
    const bfs = (root) => {
        if(!root) return true
        let queue = [root]
        let ret = true
        let depth = 1
        while(queue.length) {
            let len = queue.length
            let flag = false  
            for(let i=0;i<len;i++) {
                let node = queue.shift()
                // 当存在右子树，却无左子树
                if(!node.left && node.right) return false
                // 当队列中存在叶子节点，并且当前节点有子树
                if(flag && (node.left || node.right)) return false
                // 当队列中节点为叶子节点
                if(!node.left || !node.right) {
                    flag = true
                }
                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
            }
            // 当二叉树深度并非最后一层，但是当前层节点数小于最大个数，说明有节点缺失
            if(queue.length>0 && len< 2**(depth-1)) return false
             depth++

        }
        return ret
    }
    return  bfs(root)
}