---

[!info] related notes 算法面试题型 MOC 二叉树高频题

Validate Complete Binary Tree

LeetCode: https://leetcode.cn/problems/check-completeness-of-a-binary-tree/

判定规则（BFS）

按层遍历：

1. 如果出现“有右孩子但没有左孩子”，一定不是完全二叉树。
2. 一旦出现某个节点孩子不全（缺左或缺右），后续遇到的所有节点都必须是叶子节点，否则不是。

用一个布尔变量 mustBeLeaf 表示是否已经进入“后续必须全是叶子”的阶段。

Java Template

import java.util.*;

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean mustBeLeaf = false;

        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            TreeNode l = cur.left;
            TreeNode r = cur.right;

            if (l == null && r != null) return false;
            if (mustBeLeaf && (l != null || r != null)) return false;

            if (l != null) q.add(l);
            if (r != null) q.add(r);
            if (l == null || r == null) mustBeLeaf = true;
        }
        return true;
    }
}

Related

• 完全二叉树节点个数
• 二叉树高频题