958. 二叉树的完全性检验

给你一棵二叉树的根节点 root ，请你判断这棵树是否是一棵 完全二叉树 。

在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 h 层）中可以包含 1 到 2h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，节点值为 {1} 和 {2,3} 的两层），且最后一层中的所有节点（{4,5,6}）尽可能靠左。

示例 2：

输入：root = [1,2,3,4,5,null,7]
输出：false
解释：值为 7 的节点不满足条件「节点尽可能靠左」。

提示：

• 树中节点数目在范围 [1, 100] 内
• 1 <= Node.val <= 1000

BFS

对于一个完全二叉树，层序遍历的过程中遇到第一个空节点之后不应该再出现非空节点

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean encounteredNull = false;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            if (node == null) {
                encounteredNull = true;
            } else {
                if (encounteredNull) {
                    return false;  // 如果之前已经遇到过空节点，但现在遇到非空节点，则不满足完全二叉树的条件
                }
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return true;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

DFS

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) return true;

        int totalNodes = countNodes(root);  // 计算总节点数
        // 先计算出总结点数，再在dfs中检查index是否大于总结点数。
        return dfs(root, 1, totalNodes);
    }

    // 递归计算二叉树的节点总数
    private int countNodes(TreeNode node) {
        if (node == null) return 0;
        return 1 + countNodes(node.left) + countNodes(node.right);
    }

    // 深度优先搜索检查每个节点的索引是否符合完全二叉树的要求
    private boolean dfs(TreeNode node, int index, int totalNodes) {
        if (node == null) return true;
        if (index > totalNodes) return false;  // 如果节点索引超过总节点数，返回 false
        return dfs(node.left, 2 * index, totalNodes) && dfs(node.right, 2 * index + 1, totalNodes);
    }
}