958.二叉树的完全性检验

dfs

二叉树的完全性检验问题要求我们检查一棵二叉树是否是完全二叉树。完全二叉树的定义是：在完全二叉树中，所有层除了最后一层必须是完全填满的，最后一层的所有节点必须尽可能靠左。

可以通过广度优先搜索 (BFS) 来解决这个问题。我们使用一个队列来遍历树的节点，并记录我们是否遇到了一个空节点。如果在遇到空节点之后仍然遇到非空节点，则说明这不是一个完全二叉树。

var isCompleteTree = function (root) {
    if (!root) return true;
    let queue = [root];
    let hasNull = false;
    while (queue.length) {
        const node = queue.shift();

        if (node === null) {
            hasNull = true;
        } else {
            if (hasNull) return false;
            queue.push(node.left);
            queue.push(node.right);
        }
    }
    return true;
};

解释

1. 队列初始化：首先，我们初始化一个队列，将根节点入队。
2. 广度优先搜索：我们使用一个 while 循环来遍历队列中的所有节点。
   • 空节点检查：如果当前节点是 null，我们设置 foundNull 标志为 true，表示我们已经遇到过一个空节点。
   • 非空节点检查：如果当前节点不是 null，但之前已经遇到过空节点（即 foundNull 为 true），说明这不是一个完全二叉树，返回 false。
   • 继续遍历：将当前节点的左子节点和右子节点依次入队。
3. 遍历结束：如果队列遍历结束后没有违反完全二叉树的条件，则返回 true。

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树的节点数。我们需要遍历每个节点一次。
• 空间复杂度：O(N)，最坏情况下队列中可能包含所有节点。

bfs

对比最后节点索引 === 节点数量-1

var isCompleteTree = function (root) {
    if (!root) return true;

    let maxIndex = 0;
    let nodeCount = 0;

    const dfs = (node, index) => {
        if (!node) return;
        nodeCount++;
        maxIndex = Math.max(maxIndex, index);
        dfs(node.left, 2 * index + 1);
        dfs(node.right, 2 * index + 2);
    };

    dfs(root, 0);

    return maxIndex === nodeCount - 1;
};