演算法與資料結構
  • 簡介
  • 前言
    • 事前準備
    • 資料結構場景
    • 複雜度分析
      • 時間複雜度
      • 空間複雜度
  • 分類題型
    • Array 陣列
      • 88. Merge Sorted Array
      • 1089. Duplicate Zeros
      • 941. Valid Mountain Array
      • 1710. Maximum Units on a Truck
      • 54. Spiral Matrix
      • 73. Set Matrix Zeroes
      • 498. Diagonal Traverse
      • 238. Product of Array Except Self
      • HackerRank Counting Valleys
      • 1089. Duplicate Zeros
    • Backtrack 回溯法
      • 51. & 52. N Queens
      • 37. Sudoku Solver
      • 77. Combinations
      • 39. Combination Sum
        • 40. Combination Sum II
        • 216. Combination Sum III
      • 78. Subsets
        • 90. Subsets II
      • 46. Permutations
        • 47. Permutations II
      • 22. Generate Parentheses
      • 1087. Brace Expansion
      • 332. Reconstruct Itinerary
      • 489. Robot Room Cleaner
      • 17. Letter Combinations of a Phone Number
      • 79. Word Search
        • 212. Word Search II
      • 425. Word Squares
      • 1219. Path with Maximum Gold
      • 247. Strobogrammatic Number II
    • Binary Search 二分搜索
      • Rotated Array 旋轉陣列問題
        • 33. Search in Rotated Sorted Array
        • 81. Search in Rotated Sorted Array II
        • 153. Find Minimum in Rotated Sorted Array
        • 154. Find Minimum in Rotated Sorted Array II
      • 374. Guess Number Higher or Lower
      • 704. Binary Search
      • 34. Find First and Last Position of Element in Sorted Array
      • 69. Sqrt(x)
      • 367. Valid Perfect Square
      • 374. Guess Number Higher or Lower
      • 278. First Bad Version
      • 162. Find Peak Element
      • 852. Peak Index in a Mountain Array
      • 35. Search Insert Position
      • 875. Koko Eating Bananas
      • 1011. Capacity To Ship Packages Within D Days
      • 173. Binary Search Tree Iterator
      • 1586. Binary Search Tree Iterator II
    • Dynamic Programming 動態規劃
      • 509. Fibonacci Number
      • 70. Climbing Stairs
      • 55. Jump Game
      • 62. Unique Paths
      • 64. Minimum Path Sum
      • 174. Dungeon Game
      • 91. Decode Ways
      • 72. Edit Distance
      • 221. Maximal Square
      • 329. Longest Increasing Path in a Matrix
      • 198. House Robber
        • 213. House Robber II
      • 1109. Corporate Flight Bookings
      • 983. Minimum Cost For Tickets
      • 1143. Longest Common Subsequence
        • 583. Delete Operation for Two Strings
        • 712. Minimum ASCII Delete Sum for Two Strings
      • 53. Maximum Subarray
      • 152. Maximum Product Subarray
      • 975. Odd Even Jump
      • 115. Distinct Subsequences
      • 416. Partition Equal Subset Sum
      • 10. Regular Expression Matching
      • 651. 4 Keys Keyboard
    • Hash Table/Set 雜湊表
      • 242. Valid Anagram
      • 49. Group Anagrams
      • 217. Contains Duplicate
        • 219. Contains Duplicate II
        • 220. Contains Duplicate III
      • 187. Repeated DNA Sequences
      • 1170. Compare Strings by Frequency of the Smallest Character
      • 448. Find All Numbers Disappeared in an Array
      • 560. Subarray Sum Equals K
      • 1010. Pairs of Songs With Total Durations Divisible by 60
    • Heap 堆
      • 347. Top K Frequent Elements
      • 692. Top K Frequent Words
      • 973. K Closest Points to Origin
      • 128. Longest Consecutive Sequence
      • 1167. Minimum Cost to Connect Sticks
    • Linked List 鏈結串列
      • 876. Middle of the Linked List
      • 21. Merge Two Sorted Lists
        • 23. Merge k Sorted Lists
      • 148. Sort List
      • 206. Reverse Linked List
        • 92. Reverse Linked List II
    • Stack 棧
      • 20. Valid Parentheses
      • 394. Decode String
      • 84. Largest Rectangle in Histogram
      • 155. Min Stack
    • String 字串
      • 43. Multiply Strings
      • 344. Reverse String
      • 726. Number of Atoms
      • 8. String to Integer (atoi)
      • 12. Integer to Roman
      • 696. Count Binary Substrings
    • Tree 樹
      • Breadth-first search 廣度優先搜索
        • 111. Minimum Depth of Binary Tree
        • 200. Number of Islands
        • 752. Open the Lock
        • 279. Perfect Squares
        • 286. Walls and Gates
        • 417. Pacific Atlantic Water Flow
        • 994. Rotting Oranges
        • 429. N-ary Tree Level Order Traversal
        • 116. Populating Next Right Pointers in Each Node
        • 117. Populating Next Right Pointers in Each Node II
        • 430. Flatten a Multilevel Doubly Linked List
        • 1135. Connecting Cities With Minimum Cost
      • Preorder 前序遍歷
        • 105. Construct Binary Tree from Preorder and Inorder Traversal
        • 144. Binary Tree Preorder Traversal
        • 589. N-ary Tree Preorder Traversal
        • 255. Verify Preorder Sequence in Binary Search Tree
      • Inorder 中序遍歷
        • 94. Binary Tree Inorder Traversal
        • 426. Convert Binary Search Tree to Sorted Doubly Linked List
      • Postorder 後序遍歷
        • 106. Construct Binary Tree from Inorder and Postorder Traversal
        • 145. Binary Tree Postorder Traversal
        • 590. N-ary Tree Postorder Traversal
        • 114. Flatten Binary Tree to Linked List
        • 652. Find Duplicate Subtrees
        • 124. Binary Tree Maximum Path Sum
        • 543. Diameter of Binary Tree
        • 337. House Robber III
      • BST
        • 98. Validate Binary Search Tree
        • 450. Delete Node in a BST
        • 700. Search in a Binary Search Tree
        • 701. Insert into a Binary Search Tree
        • 1373. Maximum Sum BST in Binary Tree
        • 230. Kth Smallest Element in a BST
        • 99. Recover Binary Search Tree
      • Serialization & Deserialization
        • 606. Construct String from Binary Tree
        • 536. Construct Binary Tree from String
        • 297. Serialize and Deserialize Binary Tree
        • 428. Serialize and Deserialize N-ary Tree
      • Graph 圖
        • 1971. Find if Path Exists in Graph
        • 323. Number of Connected Components in an Undirected Graph
        • 547. Number of Provinces
      • 100. Same Tree
        • 572. Subtree of Another Tree
      • 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
      • 226. Invert Binary Tree
      • 104. Maximum Depth of Binary Tree
      • 559. Maximum Depth of N-ary Tree
      • 102. Binary Tree Level Order Traversal
      • 261. Graph Valid Tree
      • 250. Count Univalue Subtrees
      • 222. Count Complete Tree Nodes
      • 112. Path Sum
      • 113. Path Sum II
      • 437. Path Sum III
    • Trie 字典樹
      • 208. Implement Trie (Prefix Tree)
      • 677. Map Sum Pairs
      • 648. Replace Words
      • 588. Design In-Memory File System
      • 642. Design Search Autocomplete System
      • 211. Design Add and Search Words Data Structure
      • 1268. Search Suggestions System
    • Two Pointers 雙指針
      • 977. Squares of a Sorted Array
      • 1095. Find in Mountain Array
      • 27. Remove Element
      • 141. Linked List Cycle
        • 142. Linked List Cycle II
      • 19. Remove Nth Node From End of List
      • 26. Remove Duplicates from Sorted Array
      • 83. Remove Duplicates from Sorted List
      • 283. Move Zeroes
    • Sliding Window 滑動窗口
      • 3. Longest Substring Without Repeating Characters
      • 76. Minimum Window Substring
      • 567. Permutation in String
      • 438. Find All Anagrams in a String
      • 424. Longest Repeating Character Replacement
      • 485. Max Consecutive Ones
      • 1004. Max Consecutive Ones III
      • 904. Fruit Into Baskets
      • 1248. Count Number of Nice Subarrays
      • 1358. Number of Substrings Containing All Three Characters
      • 1234. Replace the Substring for Balanced String
      • 930. Binary Subarrays With Sum
      • 209. Minimum Size Subarray Sum
      • 992. Subarrays with K Different Integers
      • 713. Subarray Product Less Than K
      • 862. Shortest Subarray with Sum at Least K
      • 239. Sliding Window Maximum
      • 159. Longest Substring with At Most Two Distinct Characters
      • 340. Longest Substring with At Most K Distinct Character
      • 992. Subarrays with K Different Integers
    • Bit Manipulation 位元運算
      • 136. Single Number
      • 7. Reverse Integer
      • 191. Number of 1 Bits
    • Math 數學
      • 553. Optimal Division
      • 204. Count Primes
      • 372. Super Pow
      • 829. Consecutive Numbers Sum
      • 1492. The kth Factor of n
    • Other 其他
      • 31. Next Permutation
      • 1446. Consecutive Characters
      • 386. Lexicographical Numbers
      • 269. Alien Dictionary
      • 48. Rotate Image
      • 157. Read N Characters Given Read4
        • 158. Read N Characters Given Read4 II - Call multiple times
      • 246. Strobogrammatic Number
    • Object Oriented Design 物件導向設計
      • 710. Random Pick with Blacklist
      • 380. Insert Delete GetRandom O(1)
      • 271. Encode and Decode Strings
      • 348. Design Tic-Tac-Toe
  • 經典題目
    • Best Time to Buy and Sell Stock 股票買賣問題
      • 121. Best Time to Buy and Sell Stock
      • 122. Best Time to Buy and Sell Stock II
      • 123. Best Time to Buy and Sell Stock III
      • 188. Best Time to Buy and Sell Stock IV
      • 309. Best Time to Buy and Sell Stock with Cool down
      • 714. Best Time to Buy and Sell Stock with Transaction Fee
    • Palindrome 回文
      • 125. Valid Palindrome
      • 680. Valid Palindrome II
      • 266. Palindrome Permutation
      • 9. Palindrome Number
      • 866. Prime Palindrome
      • 5. Longest Palindromic Substring
      • 647. Palindromic Substrings
      • 516. Longest Palindromic Subsequence
      • 1930. Unique Length-3 Palindromic Subsequences
      • 234. Palindrome Linked List
    • Time Intervals 時間區間問題
      • 252. Meeting Rooms
      • 253. Meeting Rooms II
      • 56. Merge Intervals
      • 57. Insert Interval
      • 495. Teemo Attacking
      • 759. Employee Free Time
      • 986. Interval List Intersections
      • 435. Non-overlapping Intervals
      • 452. Minimum Number of Arrows to Burst Balloons
      • 729. My Calendar I
      • 731. My Calendar II
      • 732. My Calendar III
      • 163. Missing Ranges
      • 1024. Video Stitching
    • Calculator 計算機問題
      • 224. Basic Calculator
      • 227. Basic Calculator II
      • 772. Basic Calculator III
    • Add One 加一問題
      • 66. Plus One
      • 67. Add Binary
      • 369. Plus One Linked List
      • 2. Add Two Numbers
        • 445. Add Two Numbers II
      • 989. Add to Array-Form of Integer
    • Clone Graph 複製圖形
      • 133. Clone Graph
      • 1490. Clone N-ary Tree
      • 138. Copy List with Random Pointer
      • 1485. Clone Binary Tree With Random Pointer
    • Cache 快取問題
      • 146. LRU Cache 最久未使用演算法
      • 460. LFU Cache 最近最少使用演算法
    • n Sum 問題
      • 1. 2 Sum
      • 15. 3Sum
      • 18. 4Sum
      • 454. 4 Sum II
      • 167. Two Sum II - Input array is sorted
      • 170. Two Sum III - Data structure design
      • 653. Two Sum IV - Input is a BST
      • 16. 3Sum Closest
      • 259. 3Sum Smaller
      • 16. 3Sum Closest
    • Lowest Common Ancestor of a Binary Tree 最近共同祖先問題
    • The Maze 球滾迷宮問題
      • 490. The Maze
      • 505. The Maze II
    • Find Median 尋找中位數
      • 295. Find Median from Data Stream
      • 4. Median of Two Sorted Arrays
    • Course 課程問題
      • 207. 210. Course Schedule I & II
      • 1136. Parallel Courses
    • Coin Change 零錢問題
      • 322. Coin Change
      • 518. Coin Change 2
    • Binary Indexed Tree 樹狀陣列或二元索引樹
      • 303. Range Sum Query - Immutable
      • 307. Range Sum Query - Mutable
      • 315. Count of Smaller Numbers After Self
    • Longest Increasing Subsequence 最長遞增子序列的問題
      • 300. Longest Increasing Subsequence
      • 354. Russian Doll Envelopes
      • 673. Number of Longest Increasing Subsequence
    • Robot Bounded In Circle 掃地機器人
    • Containing Water 裝水問題
      • 11. Container With Most Water
      • 42. Trapping Rain Water
      • 755. Pour Water
    • Word Ladder 文字梯問題
      • 127. Word Ladder
      • 126. Word Ladder II
    • Egg Drop 高樓扔雞蛋
    • Custom sorting 排序技巧
      • 937. Reorder Data in Log Files
    • Word Break 字串組合問題
      • 139. Word Break
      • 140. Word Break II
      • 472. Concatenated Words
  • 常見演算法
    • Sorting 排序
      • Merge Sort (Accepted)
      • Quick Sort (Accepted)
      • Heap Sort (Accepted)
      • Bubble Sort (TLE)
      • Insertion Sort (TLE)
      • Selection Sort (TLE)
    • Shuffle Array 打亂陣列內的元素
    • 池塘抽樣
      • 382. Linked List Random Node
      • 398. Random Pick Index
  • Python 技巧
    • 陣列複製
    • 矩陣操作
      • 向矩陣中的四個方向移動
      • 矩陣遍歷的方法
Powered by GitBook
On this page

Last updated 2 years ago

BFS 的優勢在於如果要查找圖或是樹的最短距離，BFS 可以在找到目標後快速地停止探索。DFS 在查找最短距離時，要把所有的可行解都找到，才能比較出最短路徑。

有些題目並沒有很明確的是圖或是樹的題目，但是其實也是要尋找最短路徑，這種題目的困難在於我們要如後透過當下的狀態，判斷出子樹長什麼樣子。

另外 BFS 還有一個優勢，那就是 BFS 是可以做到多點同時出發的，把不同的出發點視作是同一層即可，有些題目甚至一定要這樣做，因為這樣可以節省很多時間。

752. Open the Lock
Word Ladder 文字梯問題
286. Walls and Gates
417. Pacific Atlantic Water Flow
994. Rotting Oranges
PreviousTree 樹Next111. Minimum Depth of Binary Tree
  1. 分類題型
  2. Tree 樹

Breadth-first search 廣度優先搜索