DFS+BFS

BFS

BFS使用队列,把每个还没有搜索到的点依次放入队列,然后再弹出队列的头部元素当做当前遍历点。

来三道题理解下:

1.二叉树的层次遍历:

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

我的答案:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        #BFS
        queue = collections.deque()#存储每层节点,用来遍历下层节点
        queue.append(root)
        res = []
        while queue:
            size = len(queue)
            level = []#临时列表,存储每层节点
            for _ in range(size):
                cur = queue.popleft()#每次循环过程,从左向右依次弹出当前层的结点
                if not cur:
                    continue
                level.append(cur.val)
                queue.append(cur.left)
                queue.append(cur.right)
            if level:
                res.append(level)
        return res

2.N叉树的层次遍历:

https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

我的答案:

"""
# 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]]:
        queue = collections.deque()
        queue.append(root)
        res = []
        while queue:
            length = len(queue)
            level = []
            for _ in range(length):
                cur = queue.popleft()
                if not cur:
                    continue
                level.append(cur)
                queue.append(cur.children)
            if level:
                res.append(level)
        return res

3.二叉树的锯齿形层次遍历

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = collections.deque()
        queue.append(root)
        res = []
        depth = 1
        while queue:
            length = len(queue)
            level = []
            depth += 1
            for _ in range(length):
                cur = queue.popleft()
                if not cur:
                    continue
                level.append(cur.val)
                queue.append(cur.left)
                queue.append(cur.right)
            #对层数的奇偶进行判断,确定输出顺序
            if level and depth % 2 == 1:
                res.append(level[::-1])
            if level and depth % 2 == 0:
                res.append(level)
        return res

三道题我都是用同样的风格写出来的,循环易于理解

BFS已关闭评论