LeetCode958-二叉树的完全性检验

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/check-completeness-of-a-binary-tree/

中文链接：https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree/

题目详述

给定一个二叉树，确定它是否是一个完全二叉树。

百度百科中对完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

示例 1：

输入：[1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
示例 2：

输入：[1,2,3,4,5,null,7]
输出：false
解释：值为 7 的结点没有尽可能靠向左侧。

提示：

树中将会有 1 到 100 个结点。

题目详解

运用 BFS，当遇到一个空结点的时候，后面如果有结点必须全部为空结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_00958 {

    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.peek() != null) {
            TreeNode node = queue.poll();
            queue.offer(node.left);
            queue.offer(node.right);
        }
        while (!queue.isEmpty() && queue.peek() == null) {
            queue.poll();
        }
        return queue.isEmpty();
    }
}
  • 根据完全二叉树的性质，若根结点的下标记为 1，则当前结点的下标为 i 时，其左右孩子结点下标分别为 2 * i、2 * i + 1。并且完全二叉树的下标全部不超过其结点个数。
  • 可以先求出完全二叉树的结点个数，然后进行递归判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00958 {

    public boolean isCompleteTree(TreeNode root) {
        int size = treeSize(root);
        return dfs(root, 1, size);
    }

    private boolean dfs(TreeNode root, int i, int size) {
        if (root == null) {
            return true;
        }
        if (i > size) {
            return false;
        }
        return dfs(root.left, i << 1, size) && dfs(root.right, i << 1 | 1, size);
    }

    private int treeSize(TreeNode root) {
        return root == null ? 0 : 1 + treeSize(root.left) + treeSize(root.right);
    }
}