一道经典的BFS

Note swift algorithm leetcode tree BFS

Word count: 402Reading time: 1 min

 2021/09/05 

剑指 Offer 32 - I. 从上到下打印二叉树，要求按照每层从左至右的顺序打印，也就是BFS（广度优先搜索）。记录一下BFS+队列的方案

题目描述：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

我们很容易想到使用BFS，需要注意的是，BFS比较难以使用递归实现，一开始尝试了递归，但发现写起来比较繁琐。使用队列可以很快地实现BFS。
以下为代码

class Solution {
    var res = [Int]()
    func levelOrder(_ root: TreeNode?) -> [Int] {
        
        var queue = [TreeNode]()
        if root == nil {
            return res
        }
        queue.append(root!)
        bfs(root,&queue)
        return res
    }

    func bfs(_ head: TreeNode?, _ arr: inout Array<TreeNode>) {
        while (arr.count > 0) {
            let node = arr[0]
            if let left = node.left {
                arr.append(left)
            }
            if let right = node.right {
                arr.append(right)
            }
            res.append(node.val)
            arr.remove(at:0)
        }
    }
}

利用队列FIFO的特性，将节点的左右节点按序加入队列，打印较先进入队列的节点值，并将它移出队列，就完成了二叉树从上到下，每层按左向右的顺序的遍历，也就是层次遍历。

总结

二叉树的前序遍历、中序遍历、后序遍历分别按照根左右、左根右、左右根的顺序，是二叉树一个基础但又重要的知识点，需要熟记和掌握代码实现。其中前序遍历就是DFS（深度优先搜索），层次遍历就是BFS（广度优先搜索）

Next Post

课程表
Previous Post

快速排序

CATALOG

1. 总结