难度：★★★☆☆
类型：树
方法：宽度优先搜索

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

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

若设二叉树的深度为 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 个结点。

解答

一个二叉树是完全二叉树，我们把二叉树的所有结点按照从上到下，从左往右的顺序编号，这些编号一定是连续的，根据这一原则，可以做二叉树的完全性判定。

对于编号为idx的结点，它的左子树和右子树的根节点的编号一定是idx2和idx2+1，这是由二叉树的结构决定的。

设n是结点数，如果编号连续，则存在编号之和等于 n * (n + 1) // 2

我们用宽度优先搜索可以实现整个遍历过程。

class Solution:
    def isCompleteTree(self, root):
        res = []
        s = [(root, 1)]

        while s:
            cur, idx = s.pop()
            if cur:
                res.append(idx)
                s.append((cur.left, 2 * idx))
                s.append((cur.right, 1 + 2 * idx))

        n = len(res)
        return sum(res) == n * (n + 1) // 2

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析