Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
判断一颗二叉树是否是完全的,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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理