-
Notifications
You must be signed in to change notification settings - Fork 0
/
LC_Binary_Tree_Level_Order_Traversal.py
49 lines (47 loc) · 1.37 KB
/
LC_Binary_Tree_Level_Order_Traversal.py
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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
"""
Visit Level by level. Store the current nodes visited in the answers.
Then navigate the next child level
"""
class Solution:
def levelOrder(self, root):
Ans = []
level = [root]
while root and level:
Current = []
Child = []
for item in level:
Current.append(item.val)
if (item.left):
Child.append(item.left)
if (item.right):
Child.append(item.right)
Ans.append(Current)
level = Child
return Ans
class Solution:
def levelOrder(self, root):
res = []
# add it to a queue
q = collections.deque()
q.append(root)
while q:
# Visit level by level
qLen = len(q)
# keep track of all items in the level
level = []
for i in range(qLen):
node = q.popleft()
if node:
level.append(node.val)
q.append(node.left)
q.append(node.right)
if level:
# Add it to the answer
res.append(level)
return res