小学生都能看懂的题解 | #判断是不是完全二叉树#

故事背景

想象你有一个篮球队，教练要求队员们分成几排站立。每一排的人数尽可能多，最后一排的人数不一定满，但必须从左边开始站。现在我们要检查队员们是否按照教练的要求站好了队。

我们的树

我们的树就像队员们分排站立的样子，每个节点代表一个队员。例如：

完全二叉树的例子：
        1
       / \
      2   3
     / \ / \
    4  5 6  7

不是完全二叉树的例子：
        1
       / \
      2   3
     / \   \
    4  5   6

判断规则

要判断一棵树是否是一个完全二叉树，我们需要遵循以下规则：

1. 除了最后一层，其他每一层的节点数都达到最大。
2. 最后一层的叶子节点必须连续集中在最左边。

如何实现

让我们用一个故事来说明这个过程：

1. 从根节点开始：从树的根节点开始，用广度优先搜索（BFS）的方式一层一层地检查。
2. 记录遇到空节点的时间：一旦遇到空节点（null），就标记下来，之后遇到的节点都应该在标记的节点的右边。
3. 检查最后一层：如果在标记之后还遇到了非空节点，则不是完全二叉树。

代码解释

让我们看看具体的代码实现：

java深色版本import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int x) {
        val = x;
    }
}

public class CompleteBinaryTreeChecker {
    // 判断是否为完全二叉树的方法
    public boolean isCompleteBinaryTree(TreeNode root) {
        if (root == null) {
            return true;
        }

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

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

            // 如果已经遇到了空节点，那么后面不能再有非空节点
            if (encounteredNull && current != null) {
                return false;
            }

            if (current == null) {
                encounteredNull = true;
            } else {
                queue.offer(current.left);
                queue.offer(current.right);
            }
        }

        return true;
    }
}

详细的解释

1. 检查是否有节点：如果树为空（没有节点），则认为它是完全二叉树。
2. 广度优先搜索（BFS）：用一个队列来逐层遍历树中的节点。
3. 记录遇到空节点的时间：一旦遇到空节点，就标记为true。
4. 检查节点：检查每个节点，一旦遇到空节点，之后就不能再有非空节点。