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

每天分享一个LeetCode题目
每天 5 分钟,一起进步!
LeetCode 层序遍历,地址:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
树结点类
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
|
层序遍历
层序遍历比较重要!
第一点,层序本身就是一种 BFS 的思想,作为最为基础的一个题目,校招中很多时候会被问到;
第二点,在解决一些其他类型的题目的时候,BFS 的思想可以作为很多题目的基础解法,这个在后面的题目中会很多次的用到。
通常解法思路(利用队列进行辅助):
1.初始化一个队列queue,然后将头结点入队;
2.队列 queue 出队首元素 node,并且打印
3.判断结点 node 是否有左右孩子。如果有,左右孩子依次入队,然后执行第 2 点。否则,直接执行第 2 点
实现的代码
1 2 3 4 5 6 7 8 9 10 11
| def level_order_traverse(self, head): if not head: return queue = [head] while len(queue) > 0: tmp = queue.pop(0) print(tmp.value, end=" ") if tmp.left: queue.append(tmp.left) if tmp.right: queue.append(tmp.right)
|
而题目中,要求是这样的形式输出。即:将每一行作为一个列表输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 二叉树:[3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7 返回其层序遍历结果:
[ [3], [9,20], [15,7] ]
|
咱么应该在输出的部分做一些改变,需要在遍历到每行的时候,进行单独保存,之后合并到最终的数组当中。
单独保存的部分,进行循环遍历,将下一层的结点更新到另外一个数组当中。
看代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution(object): def levelOrder(self, root): res = [] if not root: return res queue = [root] while queue: tmp_queue = [] tmp_res = [] for node in queue: tmp_res.append(node.val) if node.left: tmp_queue.append(node.left) if node.right: tmp_queue.append(node.right) queue = tmp_queue res.append(tmp_res) return 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
|
class TreeNode(object): def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
class Solution(object): def levelOrder(self, root): res = [] if not root: return res queue = [root] while queue: tmp_queue = [] tmp_res = [] for node in queue: tmp_res.append(node.val) if node.left: tmp_queue.append(node.left) if node.right: tmp_queue.append(node.right) queue = tmp_queue res.append(tmp_res) return 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.levelOrder(root))
|
最后
在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取
有任何问题,欢迎随时交流!!!