手撕Leetcode #958——Python

958. 二叉树的完全性检验

题目描述：给定一个二叉树，确定它是否是一个完全二叉树。

解题思路：
这道题我们采用迭代的思想，一层一层地去检验完全二叉树。其实就是检查每一层是否“左对齐”。从根节点开始，在队列里存储它的子结点，如果是None，也存None。那么在某一层，如果出现了None夹在非None结点中间，那么就不是完全二叉树。

看代码：

import collections
class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        que = collections.deque()
        que.append(root)
        prev = que
        while que:
            curr = que.popleft()
            # 前一个结点是None，当前结点不是None
            if prev is None and curr:
                return False
            if curr:
                que.append(curr.left)
                que.append(curr.right)
            prev = curr
        return True

时间复杂度：O(N)，即结点数；
空间复杂度：O(N)，也是结点数。