题目
You are given a binary tree:
class Node:
def __init__(self, L, R, n):
self.left = L
self.right = R
self.value = n
Your task is to return the list with elements from tree sorted by levels, which means the root element goes first, then root children (from left to right) are second and third, and so on.
Return empty list if root is None
.
Example 1 - following tree:
2
8 9
1 3 4 5
Should return following list:
[2,8,9,1,3,4,5]
Example 2 - following tree:
1
8 4
3 5
7
Should return following list:
[1,8,4,3,5,7]
我的答案
from collections import deque
def tree_by_levels(node):
if not node:
return []
else:
res = []
d = deque(maxlen=1000)
d.append(node)
while len(d) > 0:
if d[0] and not isinstance(d[0], int):
res.append(d[0].value)
d.append(d[0].left)
d.append(d[0].right)
elif d[0] and isinstance(d[0], int):
res.append(d[0])
d.popleft()
return res
这道题非常适合用队列来解决
其他精彩答案
from collections import deque
def tree_by_levels(node):
if not node:
return []
res, queue = [], deque([node,])
while queue:
n = queue.popleft()
res.append(n.value)
if n.left is not None:
queue.append(n.left)
if n.right is not None:
queue.append(n.right)
return res
def tree_by_levels(node):
p, q = [], [node]
while q:
v = q.pop(0)
if v is not None:
p.append(v.value)
q += [v.left,v.right]
return p if not node is None else []