首页 > 代码库 > Leetcode - 广度优先遍历专题
Leetcode - 广度优先遍历专题
> 基础
1. 广度遍历优先是从给定的root节点开始，逐层次的向下访问各个节点；
2. 实现的方式是通过队列的先进先出，将从root节点开始的左孩子和右孩子压入到队列中，并顺序取出；
3. 由于是用队列实现，因此不存在用递归实现的方式。
下面是基本的广度遍历优先算法：
1 def breadthFirstSearch(root): 2 queue = [] 3 queue.append(root) 4 while queue: 5 node = queue[0] 6 queue.pop(0) 7 print (‘%d ‘ % node.data) 8 if node.left: 9 queue.append(node.left)10 if node.right:11 queue.append(node.right)
> Leetcode -
Binary Tree Level Order Traversal
Note：这是一道二叉树的广度优先遍历练习题，不同之处在于要分辨出每个Node所在的深度，并给出每个深度所有Node的集合。解题思路有两种，一种是使用两个队列，分别称之为主队列和副队列，循环主队列里的所有节点，并把所有的孩子放在副队列中。直到当主队列为空时，把副队列的所有结点赋给主队列，清空副队列，并进入到下一级深度的循环。还有一种是使用flag，在root结点后加入flag，然后每次访问到flag的时候，就意味着访问到了该深度所有的Node，并且下一个深度的所有Node都加入到了队列中，这时再加入一个flag，依此循环。这里使用第二种方法。
Answer：
1 def levelOrder(root): 2 if root is []: 3 return [] 4 flag = TreeNode(65536) 5 queue, line, res = [], [], [] 6 queue.append(root) 7 queue.append(flag) 8 while queue: 9 node = queue[0]10 queue.pop(0)11 if node.val is not 65536:12 line.append(node.val)13 if node.left:14 queue.append(node.left)15 if node.right:16 queue.append(node.right)17 else:18 res.append(line)19 if not queue:20 return res21 queue.append(flag)22 line = []
> Leetcode -
Binary Tree Level Order Traversal II
Note: 本题和上一道题的基本思路相似，唯一的不同是返回值是从最深一层的结点向root结点的方向，只要在插入res的时候位置选择在最开始就可以了。这里尝试使用上面提到的两个队列的实现方式。
Answer：
1 def levelOrderBottom(root): 2 if root is []: 3 return [] 4 queue, queue2, line, res = [], [], [], [] 5 queue.append(root) 6 while queue: 7 node = queue[0] 8 queue.pop(0) 9 line.append(node.val)10 if node.left:11 queue2.append(node.left)12 if node.right:13 queue2.append(node.right)14 if not queue:15 res.insert(0, line) # insert the nodes from front16 queue, queue2, line = queue2, [], []17 return res
> Leetcode -
Binary Tree Zigzag Level Order Traversal
Note：这道题是要按照Z字形的方式访问各个Node，我在最初写的时候犯了一个错误，我是分单双将每层的Node按照正或反的方向记录到队列中，这样会有一个问题，比如针对下面的输入[1,2,3,4,#,#,5]，由于我的第二层结点是以right->left方向记录的，也就是到第二层为止输出为[1,3,2]；在将下一深度的结点入队的时候，我就是先访问的3，后访问的2，因此5先进入，4后进入，这样第三级由于是left->right输出的，我的最终输出就是[[1], [3, 2], [5, 4]]，而正确的输出其实是[[1], [3, 2], [4, 5]]。其实这个问题可以和之前的很类似，只是在将line压入res的时候，隔行做一下python list的反转就可以了。
Answer：
1 def zigzagLevelOrder(root): 2 if root is []: 3 return [] 4 flag = TreeNode(65536) 5 queue, line, res = [], [], [] 6 direction = 0 7 queue.append(root) 8 queue.append(flag) 9 while queue:10 node = queue[0]11 queue.append(0)12 if node.val is not 65536:13 line.append(node.val) 14 if node.left:15 queue.append(node.left)16 if node.right:17 queue.append(node.right)18 else:19 if direction % 2 == 0:20 res.append(line)21 else:22 res.append(line[::-1])23 if not queue:24 return res25 queue.append(flag)26 line = []27 direction += 1
Leetcode - 广度优先遍历专题