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 CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups See all bfs problems: #bfs Review: BFS ProblemsLintCode: Social NetworkLintCode: Police DistanceLintcode: Movie NetworkLintCode: Maximum Association SetLintCode: Island CityLintCode: Deliver The MessageLeetCode: Word Ladder IILeetCode: Word LadderLeetCode: Web CrawlerLeetCode: Walls and GatesLeetCode: Two Sum IV – Input is a BSTLeetCode: Tree DiameterLeetCode: Trapping Rain Water IILeetCode: The Maze IIILeetCode: The Maze IILeetCode: The MazeLeetCode: Symmetric TreeLeetCode: Sliding PuzzleLeetCode: Similar String GroupsLeetCode: Shortest Path with Alternating ColorsLeetCode: Shortest Path in Binary MatrixLeetCode: Shortest Path in a Grid with Obstacles EliminationLeetCode: Shortest Distance to a CharacterLeetCode: Shortest Distance from All BuildingsLeetCode: Shortest BridgeLeetCode: Serialize and Deserialize N-ary TreeLeetCode: Sequence ReconstructionLeetCode: Rotting OrangesLeetCode: Remove Invalid ParenthesesLeetCode: Push DominoesLeetCode: Print Binary TreeLeetCode: Path SumLeetCode: Parallel CoursesLeetCode: Pacific Atlantic Water FlowLeetCode: Output Contest MatchesLeetCode: Out of Boundary PathsLeetCode: Open the LockLeetCode: Numbers With Same Consecutive DifferencesLeetCode: Number of Ways of Cutting a PizzaLeetCode: Network Delay TimeLeetCode: N-ary Tree Level Order TraversalLeetCode: Minimum Time to Collect All Apples in a TreeLeetCode: Minimum Moves to Move a Box to Their Target LocationLeetCode: Minimum Knight MovesLeetCode: Minimum Height TreesLeetCode: Minimum Genetic MutationLeetCode: Maximum Score Words Formed by LettersLeetCode: Maximum Level Sum of a Binary TreeLeetCode: Maximum Depth of N-ary TreeLeetCode: Matrix Cells in Distance OrderLeetCode: Letter Case PermutationLeetCode: Knight Probability in ChessboardLeetCode: Knight DialerLeetCode: Kill ProcessLeetCode: Keys and RoomsLeetCode: Jump Game IVLeetCode: Jump Game IIILeetCode: Is Graph Bipartite?LeetCode: Graph Valid TreeLeetCode: Generalized AbbreviationLeetCode: Frog JumpLeetCode: Find the Kth Smallest Sum of a Matrix With Sorted RowsLeetCode: Find Leaves of Binary TreeLeetCode: Find Bottom Left Tree ValueLeetCode: Escape a Large MazeLeetCode: Employee ImportanceLeetCode: Directed Graph LoopLeetCode: Diagonal Traverse IILeetCode: Cousins in Binary TreeLeetCode: Course Schedule IILeetCode: Course ScheduleLeetCode: Coin ChangeLeetCode: Closest Leaf in a Binary TreeLeetCode: Cheapest Flights Within K StopsLeetCode: Champagne TowerLeetCode: Bus RoutesLeetCode: Binary Tree Zigzag Level Order TraversalLeetCode: Binary Tree Right Side ViewLeetCode: Binary Tree Level Order Traversal IILeetCode: Binary Tree Level Order TraversalLeetCode: Average of Levels in Binary TreeLeetCode: All Paths from Source Lead to DestinationLeetCode: All Nodes Distance K in Binary TreeLeetCode: 01 Matrix See more blog posts. Post Views: 8