1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
import collections
class :
"""
@param root: A Tree
@return: Level order a list of lists of integer
"""
def levelOrder(self, root):
return self.levelOrderBFSNonePointer(root)
def levelOrderDFS(self, root, level, ans):
if root:
if len(ans) < level + 1:
ans.append([])
ans[level].append(root.val)
if root.left:
self.levelOrderDFS(root.left, level + 1, ans)
if root.right:
self.levelOrderDFS(root.right, level + 1, ans)
def levelOrderBFS(self, root):
if root is None:
return []
queue = collections.deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
def levelOrderBFSDoubleQueue(self, root):
if root is None:
return []
queue1, queue2 = collections.deque([root]), collections.deque()
result = []
level = 0
while queue1 or queue2:
while queue1:
if len(result) < level + 1:
result.append([])
head = queue1.popleft()
result[level].append(head.val)
if head.left:
queue2.append(head.left)
if head.right:
queue2.append(head.right)
level += 1
queue1.extend(queue2)
queue2.clear()
return result
def levelOrderBFSNonePointer(self, root):
if root is None:
return []
queue = collections.deque([root, None])
result = []
level = 0
while len(queue) > 1:
if len(result) < level + 1:
result.append([])
head = queue.popleft()
if head == None:
queue.append(None)
level += 1
continue
result[level].append(head.val)
if head.left:
queue.append(head.left)
if head.right:
queue.append(head.right)
return result
|
近期评论