读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw

每天分享一个LeetCode题目
每天 5 分钟,一起进步!
LeetCode 层序遍历,地址:https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
树结点类
1 2 3 4 5
| class TreeNode(object): def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
|
层次遍历
还是和之前层次遍历同样的思路,需要将每一层的遍历结点作为单独的列表放置到最后的结果列表中去
之前普通的层次遍历思路可以看这里:https://mp.weixin.qq.com/s/4skiCYIhc9mKEBmNkot8wA
解法思路(利用队列):
1.初始化一个队列queue,然后将头结点入队,初始化一个结果集 res;
2.再初始化一个临时队列 level_queue 和 一个列表 level_res,循环访问队列 queue 中元素,并判断其左右孩子,如果有孩子结点依次将孩子结点入队level_queue,并且将当前结点入列表 level_res
3.将 level_queue 赋值给 queue,将 level_res 插入到结果集 res。完成一层的计算。随后再执行第 2 点
4.打印结果集 res
实现的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| def levelOrderBottom(self, root): res = [] queue = collections.deque() queue.appendleft(root) while(queue): level_queue = [] level_res = [] for node in queue: if node.left: level_queue.append(node.left) if node.right: level_queue.append(node.right) level_res.append(node.val) queue = level_queue res.insert(0, level_res) return list(res)
|
个人感觉很巧妙,但是四个初始化定义需要好好熟悉一下
完整代码
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
|
import collections
class TreeNode(object): def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
class Solution(object): def levelOrderBottom(self, root): res = [] queue = collections.deque() queue.appendleft(root) while(queue): level_queue = [] level_res = [] for node in queue: if node.left: level_queue.append(node.left) if node.right: level_queue.append(node.right) level_res.append(node.val) queue = level_queue res.insert(0, level_res) return list(res)
if __name__ == "__main__": root = TreeNode('A') node_B = TreeNode('B') node_C = TreeNode('C') node_D = TreeNode('D') node_E = TreeNode('E') node_F = TreeNode('F') node_G = TreeNode('G') node_H = TreeNode('H') node_I = TreeNode('I') root.left, root.right = node_B, node_C node_B.left, node_B.right = node_D, node_E node_C.left, node_C.right = node_F, node_G node_D.left, node_D.right = node_H, node_I
s = Solution() print(s.levelOrderBottom(root))
|
最后
在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取
有任何问题,欢迎随时交流!!!