判断一颗二叉树是否是完全的,BFS,如果碰到还有新节点能插入队列,但之前已经碰到过NULL节点,表示之前的某个子树不是完全的
1 #958
2 #Runtime: 22 ms (Beats 58.42%)
3 #Memory: 13.4 MB (Beats 71.73%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def isCompleteTree(self, root):
13 """
14 :type root: TreeNode
15 :rtype: bool
16 """
17 gap_between_nodes = False
18 q = deque([root])
19 while q:
20 s = len(q)
21 while s:
22 s -= 1
23 node = q.popleft()
24 if not node:
25 gap_between_nodes = True
26 else:
27 if gap_between_nodes:
28 return False
29 q.append(node.left)
30 q.append(node.right)
31 return True