难度：★★★☆☆
类型：树
方法：宽度优先搜索
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给定一个二叉树，确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下：
若设二叉树的深度为 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解决方案，请移步力扣中等题解析
