第 6 天
搜索与回溯算法(简单)BFS
面试题32 - I. 从上到下打印二叉树
首先我们可以知道这道题考查的是搜索算法中的BFS,要想实现BFS我们需要借助队列queue先进先出的性质。python中有一个collections的模块,其中有collections.deque(),它是一个双边列表,同时具有stack和queue的性质。下面是相关资料。
python中的collections.deque()用法和collections板块
解题思路:
先把根节点加入queue
while queue:
1 queue第一个元素出队列
2 将该元素vaule加入结果列表
3 将该元素左右节点加入queue
返回结果列表
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution: def levelOrder(self, root: TreeNode) -> List[int]: if root == None:return [] queue = collections.deque([root]) res = [] while queue: node = queue.popleft() res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res
剑指 Offer 32 - II. 从上到下打印二叉树
本题是在上一题的基础上增加了按层输出的要求,于是我在上一层的基础上在某一层把全部的元素都pop出来加到list中,并记录它的offspring,将offspring再加到queue中。
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if root == None:return [] queue = collections.deque([root]) res = [] while queue: value = [] for _ in range(len(queue)): node = queue.popleft() value.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(value) return res
剑指 Offer 32 - III. 从上到下打印二叉树 III
这道题又再上一道题的基础上增加了每隔一层数值反转的要求,我的解题思路如下:
设根节点为0层,偶数层queue从左到右一个一个弹出node,每个节点offspring从左到右一个一个添加到queue中,然后反转queue,来到了奇数层,由于反转了queue技术层node实际上是从右到左弹出,此时offspring也根据这个规则从右到左添加offspring到 queue。然后再反转queue,重复以上操作。
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if root == None:return [] queue = collections.deque([root]) res = [] layer = 1 while queue: value = [] for _ in range(len(queue)): node = queue.popleft() value.append(node.val) if layer%2 ==1: if node.left: queue.append(node.left) if node.right: queue.append(node.right) else: if node.right: queue.append(node.right) if node.left: queue.append(node.left) layer += 1 queue.reverse() res.append(value) return res
刷题心得:
在刷题中我遇到了使用List.reverse() 还是reversed(List)的困难,这里总结两者的区别
List.reverse()是列表自带的函数,只对列表有效
reversed()是Python内置函数,可以对元组,列表,字符串生效,但是返回的是迭代器,
需要经过遍历,List,或者next()等方法
1
2
3
4
5
6
7
8
9>>>bb = [1,3,5,7] >>>print(reversed(bb)) <list_reverseiterator object at 0x7fa9700a8730> >>>bb = [1,3,5,7] >>>print(list(reversed(bb))) 7,5,3,1
python 中 关于reverse() 和 reversed()的用法介绍
最后
以上就是暴躁戒指最近收集整理的关于剑指OFFER DAY6第 6 天的全部内容,更多相关剑指OFFER内容请搜索靠谱客的其他文章。
发表评论 取消回复