二叉树的完全性检验

IT服务圈儿 2023-02-06

The following article is from 数据结构和算法 Author 博哥

来源丨经授权转自数据结构和算法（ID：sjjghsf）

作者丨博哥

问题描述

来源：LeetCode第958题

难度：中等

给定一个二叉树的root，确定它是否是一个完全二叉树。在一个完全二叉树中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2^h 节点之间的最后一级 h 。

示例 1：

问题分析

我们仔细观察可以发现，完全二叉树有个特点就是除了最后一层没有被填满以外，上面的所有层都被填满，并且最后一层如果没被填满的话都是靠左的。对于这题的解题思路我们可以使用 BFS 遍历的方式，一层一层的遍历，记录每个节点的两个子节点，不需要判断是否为空，直接添加到队列中即可。对于完全二叉树来说队列中只要有一个为空，那么队列的后面就全部为空，如果队列中有空值并且后面又出现了没有空值的现象说明不是完全二叉树，我们画个图来看下，先看下完全二叉树的：

我们再来看下如果不是完全二叉树的情况：

最后再来看下代码：

public boolean isCompleteTree(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    // 如果遇到有空的则停止循环
    while (queue.peek() != null) {
        TreeNode cur = queue.poll();
        // 把子节点添加到队列，不需要判断是否为空
        queue.offer(cur.left);
        queue.offer(cur.right);
    }

    // 到这一步说明遇到空的了，我们需要判断队列中是否还有不为空的
    while (!queue.isEmpty() && queue.peek() == null)
        queue.poll();
    return queue.isEmpty();
}