[!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;
    }
}

边界

根只有左孩子可以是完全二叉树，只有右孩子则不可以。必须按左到右的 BFS 顺序应用叶子阶段规则；把同样规则直接搬到 DFS 会改变判断含义。TreeNode 由题目提供，本实现把空树视为完全二叉树。

每个节点最多访问一次，时间 O(n)，队列 O(w)。它执行结构判定，不是直接利用“输入已完全”的计数优化。

Related

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