Review: BFS Problems

Posted on February 8, 2018July 26, 2020 by braindenny

BFS is extremely useful. You may not imagine.

Here we try to compile a list of inspiring BFS problems.

Name	Comment
bfs: level=0 vs level=1
bfs first level/normal level/last level	last level would be empty
bfs with priority queue
When to collect result: before enque vs after deque
Understand the physical meaning of level	LeetCode: As Far from Land as Possible
If original grid can be changed, visited bool array might be optional	LeetCode: As Far from Land as Possible
Some BFS may not necessarily need visited hashmap: say topological BFS sort	LeetCode: Course Schedule II
BFS traverse nodes with same value of different positions	LeetCode: Jump Game IV

Code Skeleton

// Blog link: https://code.dennyzhang.com/maximum-level-sum-of-a-binary-tree
// Basic Ideas: bfs
//
// Complexity: Time O(n), Space O(n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxLevelSum(root *TreeNode) int {
    level, maxSum, res := 1, -1<<31, 0

    queue := []*TreeNode{root}
    for len(queue) != 0 {
        l := []*TreeNode{}
        sum := 0
        for _, node := range queue {
            sum += node.Val
            if node.Left != nil {
                l = append(l, node.Left)
            }
            if node.Right != nil {
                l = append(l, node.Right)
            }
        }
        if sum > maxSum {
            maxSum, res = sum, level
        }
        queue = l
        level++
    }
    return res
}

BFS in string: Letter Case Permutation
Distance with power: Cheapest Flights Within K Stops
Revisit seen nodes: Knight Probability in Chessboard
BFS with heap: Movie Network
For seen set use array, instead of a set: Is Graph Bipartite
Scan from target to original: Reach a Number
BFS with memoization: Target Sum

See all bfs problems: #bfs

See more blog posts.

Post Views: 8