python当中collections有一个deque双向队列,其popleft()可以实现从队列中出时间复杂度为o(1)
剑指 Offer 32 - I. 从上到下打印二叉树
直接使用队列,初始队列中为root,为从左到右便利则依次往队列中添加二叉树的结点即可,当队列为空则证明遍历结束
加一个结点利用popleft()队列出一个
import collections
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
dq = collections.deque()
dq.append(root)
res = []
while dq:
node = dq.popleft()
res.append(node.val)
if node.left: dq.append(node.left)
if node.right: dq.append(node.right)
return res
剑指 Offer 32 - II. 从上到下打印二叉树 II
import collections
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:return []
dq = collections.deque()
res = []
dq.append(root)
while dq:
temp = []
for _ in range(len(dq)):
i = dq.popleft()
temp.append(i.val)
if i.left: dq.append(i.left)
if i.right:dq.append(i.right)
res.append(temp)
return res
依旧使用上一题的队列,但是需要修改一个循环内的队列条件,实现逐层添加到结果,此题关键点就是使用当前层的队列长度,之后只遍历这段长度,向队列后加结点即可。
剑指 Offer 32 - III. 从上到下打印二叉树 III
上一题直接讲temp数组翻转即可
|