|
二叉树的广度优先搜索即从上到下、从左到右地进行搜索，对于层序遍历（Level Order）问题，即依次遍历第一层节点、第二层节点…等，基本可以秒杀。
广度优先搜索是通过队列来实现的，python中优先用collections.deque，因为deque的 popleft() 比列表的 pop(0) 快不少。
102. 二叉树的层序遍历
import collections
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
ans = list()
if not root:
return ans
queue = collections.deque()
queue.append(root)
while queue:
curLevel = list()
for i in range(len(queue)):
node = queue.popleft()
curLevel.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(curLevel)
return ans
从根节点开始，每个节点入队之后，在出队的时候把它的左右子节点也入队（如果非空），则该队列就完成了广度优先搜索。但是，需要把同一层的节点放到同一个数组中，方法是用一个当前层数组 curLevel，通过循环每次把同一层的节点的子节点全部入队，同时将这些节点的值记录到curLevel 中，一层节点遍历完之后将 curLevel 加入结果数组 ans 中。
107. 二叉树的层序遍历 II
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
ans = list()
if not root:
return ans
queue = collections.deque()
queue.append(root)
while queue:
curLevel = list()
for i in range(len(queue)):
node = queue.popleft()
curLevel.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(curLevel)
return ans[::-1]
唯一区别就是输出结果时倒转输出。
199. 二叉树的右视图
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
ans = list()
if not root:
return ans
queue = collections.deque()
queue.append(root)
while queue:
n = len(queue)
for i in range(n):
node = queue.popleft()
if i == n - 1:
ans.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return ans
结果需要的是每一层的最右边的数，因此循环到最右边的数时，才将节点加入结果数组 ans。
637. 二叉树的层平均值
class Solution:
def averageOfLevels(self, root: TreeNode) -> List[float]:
ans = list()
if not root:
return ans
queue = collections.deque()
queue.append(root)
while queue:
currLevel = list()
n = len(queue)
for i in range(n):
node = queue.popleft()
currLevel.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(mean(currLevel))
return ans
结果需要的是每一层的平均数，因此将平均数加入结果数组 ans。
515. 在每个树行中找最大值
class Solution:
def largestValues(self, root: TreeNode) -> List[int]:
ans = list()
if not root:
return ans
queue = collections.deque()
queue.append(root)
while queue:
currLevel = list()
n = len(queue)
for i in range(n):
node = queue.popleft()
currLevel.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(max(currLevel))
return ans
结果需要的是每一层的最大数，因此将最大数加入结果数组 ans。
429. N 叉树的层序遍历
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
import collections
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
ans = list()
if not root:
return ans
queue = collections.deque()
queue.append(root)
while queue:
curLevel = list()
for i in range(len(queue)):
node = queue.popleft()
curLevel.append(node.val)
for child in node.children:
if child:
queue.append(child)
ans.append(curLevel)
return ans
N叉数是 children 列表而二叉树是 left 和 right ，遍历 children 即可。
116. 填充每个节点的下一个右侧节点指针
class Solution:
def connect(self, root: 'Node') -> 'Node':
ans = list()
if not root:
return root
queue = collections.deque()
queue.append(root)
while queue:
curLevel = list()
for i in range(len(queue)):
node = queue.popleft()
curLevel.append(node)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
n = len(curLevel)
for i in range(n):
if i == n - 1:
continue
else:
curLevel[i].next = curLevel[i+1]
return root
层序遍历一次二叉树，然后对每一层的节点再进行遍历，将节点的 next 指向下一个节点即可。
117 . 填充每个节点的下一个右侧节点指针 II
class Solution:
def connect(self, root: 'Node') -> 'Node':
ans = list()
if not root:
return root
queue = collections.deque()
queue.append(root)
while queue:
curLevel = list()
for i in range(len(queue)):
node = queue.popleft()
curLevel.append(node)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
n = len(curLevel)
for i in range(n):
if i == n - 1:
continue
else:
curLevel[i].next = curLevel[i+1]
return root
不完美的二叉树，但是和上一题一模一样的代码。
|