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

1、解题思路

1. 层序遍历（BFS）：使用队列进行层序遍历。检查是否存在某个节点为空后，后面还有非空节点。
2. 标记法：在层序遍历时，标记第一次遇到空节点的情况。如果在标记后还遇到非空节点，则不是完全二叉树。

2、代码实现

C++

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <queue>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isCompleteTree(TreeNode* root) {
        // write code here
        if (root == nullptr) {
            return true;
        }

        queue<TreeNode*> q;
        q.push(root);
        bool hasNull = false;

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            if (node == nullptr) {
                hasNull = true;
            } else {
                if (hasNull) {
                    return false;
                }
                q.push(node->left);
                q.push(node->right);
            }
        }

        return true;
    }
};

Java

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root == null) return true;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        boolean hasNull = false;

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

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

        return true;
    }
}

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
from collections import deque

class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # write code here
        if not root:
            return True
        
        q = deque()
        q.append(root)
        has_null = False
        
        while q:
            node = q.popleft()
            
            if not node:
                has_null = True
            else:
                if has_null:
                    return False
                q.append(node.left)
                q.append(node.right)
        
        return True

3、复杂度分析

• 时间复杂度：O(n)，每个节点被访问一次。
• 空间复杂度：O(n)，队列存储节点。