958. 二叉樹的完全性檢驗

題目描述：給定一個二叉樹，確定它是否是一個完全二叉樹。

解題思路：
這道題我們采用迭代的思想，一層一層地去檢驗完全二叉樹。其實(shí)就是檢查每一層是否“左對齊”。從根節(jié)點(diǎn)開始，在隊列里存儲它的子結(jié)點(diǎn)，如果是None，也存None。那么在某一層，如果出現(xiàn)了None夾在非None結(jié)點(diǎn)中間，那么就不是完全二叉樹。

看代碼：

import collections
class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        que = collections.deque()
        que.append(root)
        prev = que
        while que:
            curr = que.popleft()
            # 前一個結(jié)點(diǎn)是None，當(dāng)前結(jié)點(diǎn)不是None
            if prev is None and curr:
                return False
            if curr:
                que.append(curr.left)
                que.append(curr.right)
            prev = curr
        return True

時間復(fù)雜度：O(N)，即結(jié)點(diǎn)數(shù)；
空間復(fù)雜度：O(N)，也是結(jié)點(diǎn)數(shù)。