連結リスト・木・バックトラッキング

トラック 2 はここから始まり、この先の問題集はどれも再帰が土台になります。連結リストと二分木は、多くの人が初めて自分自身を呼び出す関数を書く場所です。バックトラッキングは同じ考え方を広げて、すべての選択を試しては元に戻していきます。

5 つの章は、Reverse Linked List のような連結リストの問題から始まり、二分木、一般の木、バックトラッキング、再帰と分割統治へと進みます。グリッド、動的計画法、グラフに進む前に、再帰を当たり前に書けるようにしておきたい人に向いています。

292 問レーティング 1151–30185 章

書斎を開く

誰かと一緒にこの問題集を進めたいなら、ログインして書斎を開いてみてください。ヒロインが一問ずつ出題してくれます。

一、Linked List

§1.1 Linked Listの走査

問題	レーティング
1290. Convert Binary Number in a Linked List to Integer	1151
2058. Find the Minimum AND Maximum Number of Nodes Between Critical Points	1311
2181. Merge Nodes in Between Zeros	1333
725. Split Linked List in Parts	未評価
817. Linked List Components	1429

§1.2 ノードの削除

問題	レーティング
203. Remove Linked List Elements	未評価
3217. Delete Nodes From Linked List Present in Array	1342
83. Remove Duplicates From Sorted List	未評価
82. Remove Duplicates From Sorted List II	未評価
237. Delete Node in a Linked List	未評価
1669. Merge in Between Linked Lists	1428
2487. Remove Nodes From Linked List	1455

§1.3 ノードの挿入

問題	レーティング
2807. Insert Greatest Common Divisors in Linked List	1279
147. Insertion Sort List	未評価

§1.4 Linked Listの反転

問題	レーティング
206. Reverse Linked List	未評価
92. Reverse Linked List II	未評価
24. Swap Nodes in Pairs	未評価
25. Reverse Nodes in K Group	未評価
2074. Reverse Nodes in Even Length Groups	1685

§1.5 前後のTwo Pointers

問題	レーティング
19. Remove Nth Node From End of List	未評価
61. Rotate List	未評価
1721. Swapping Nodes in a Linked List	1387

§1.6 fast pointerとslow pointer

問題	レーティング
876. Middle of the Linked List	1232
2095. Delete the Middle Node of a Linked List	1324
234. Palindrome Linked List	未評価
2130. Maximum Twin Sum of a Linked List	1318
143. Reorder List	未評価
141. Linked List Cycle	未評価
142. Linked List Cycle II	未評価
457. Circular Array Loop	未評価

§1.7 Two Pointers

問題	レーティング
328. Odd Even Linked List	未評価
86. Partition List	未評価
160. Intersection of Two Linked Lists	未評価

§1.8 Linked Listのマージ

問題	レーティング
2. Add Two Numbers	未評価
445. Add Two Numbers II	未評価
2816. Double a Number Represented As a Linked List	1394
21. Merge Two Sorted Lists	未評価

§1.9 Divide and Conquer

問題	レーティング
23. Merge K Sorted Lists	未評価
148. Sort List	未評価

§1.10 総合演習

問題	レーティング
1171. Remove Zero Sum Consecutive Nodes From Linked List	1782
707. Design Linked List	未評価
146. Lru Cache	未評価
460. Lfu Cache	未評価
432. All Oone Data Structure	未評価
1206. Design Skiplist	未評価

§1.11 その他

問題	レーティング
138. Copy List with Random Pointer	未評価
382. Linked List Random Node	未評価
430. Flatten a Multilevel Doubly Linked List	未評価

二、Binary Tree

§2.1 Binary Treeの走査

問題	レーティング
144. Binary Tree Preorder Traversal	未評価
94. Binary Tree Inorder Traversal	未評価
145. Binary Tree Postorder Traversal	未評価
872. Leaf Similar Trees	1288
404. Sum of Left Leaves	未評価
671. Second Minimum Node in a Binary Tree	未評価

§2.2 トップダウン DFS（先行順）

問題	レーティング
104. Maximum Depth of Binary Tree	未評価
111. Minimum Depth of Binary Tree	未評価
112. Path Sum	未評価
129. Sum Root to Leaf Numbers	未評価
199. Binary Tree Right Side View	未評価
1448. Count Good Nodes in Binary Tree	1360
1315. Sum of Nodes with Even Valued Grandparent	1427
988. Smallest String Starting From Leaf	1429
1026. Maximum Difference Between Node AND Ancestor	1446
1022. Sum of Root to Leaf Binary Numbers	1462
623. Add One Row to Tree	未評価
1372. Longest Zigzag Path in a Binary Tree	1713
971. Flip Binary Tree to Match Preorder Traversal	1787

§2.3 ボトムアップ DFS（後行順）

問題	レーティング
104. Maximum Depth of Binary Tree	未評価
111. Minimum Depth of Binary Tree	未評価
965. Univalued Binary Tree	1178
100. Same Tree	未評価
101. Symmetric Tree	未評価
951. Flip Equivalent Binary Trees	1477
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree	未評価
110. Balanced Binary Tree	未評価
226. Invert Binary Tree	未評価
617. Merge Two Binary Trees	未評価
2331. Evaluate Boolean Binary Tree	1304
508. Most Frequent Subtree Sum	未評価
563. Binary Tree Tilt	未評価
606. Construct String From Binary Tree	未評価
2265. Count Nodes Equal to Average of Subtree	1473
1026. Maximum Difference Between Node AND Ancestor	1446
3319. K Th Largest Perfect Subtree Size in Binary Tree	1603
1339. Maximum Product of Splitted Binary Tree	1675
1372. Longest Zigzag Path in a Binary Tree	1713
1145. Binary Tree Coloring Game	1741
572. Subtree of Another Tree	未評価
1530. Number of Good Leaf Nodes Pairs	1746

§2.4 ボトムアップ DFS：ノードの削除

問題	レーティング
814. Binary Tree Pruning	1380
1325. Delete Leaves with a Given Value	1407
1110. Delete Nodes AND Return Forest	1511

§2.5 行きと帰りの両方で処理する

問題	レーティング
538. Convert Bst to Greater Tree	未評価
1038. Binary Search Tree to Greater Sum Tree	1375
865. Smallest Subtree with All the Deepest Nodes	1534
1080. Insufficient Nodes in Root to Leaf Paths	1805

§2.6 Binary Treeの直径

問題	レーティング
543. Diameter of Binary Tree	未評価
687. Longest Univalue Path	未評価
124. Binary Tree Maximum Path Sum	未評価
2385. Amount of Time for Binary Tree to Be Infected	1711

§2.7 Backtracking

問題	レーティング
257. Binary Tree Paths	未評価
113. Path Sum II	未評価
1457. Pseudo Palindromic Paths in a Binary Tree	1405
437. Path Sum III	未評価

§2.8 Lowest Common Ancestor (LCA)

問題	レーティング
235. Lowest Common Ancestor of a Binary Search Tree	未評価
236. Lowest Common Ancestor of a Binary Tree	未評価
1123. Lowest Common Ancestor of Deepest Leaves	1607
2096. Step by Step Directions From a Binary Tree Node to Another	1805

§2.9 Binary Search Tree

問題	レーティング
700. Search in a Binary Search Tree	未評価
530. Minimum Absolute Difference in Bst	未評価
783. Minimum Distance Between Bst Nodes	1303
938. Range Sum of Bst	1335
501. Find Mode in Binary Search Tree	未評価
230. Kth Smallest Element in a Bst	未評価
98. Validate Binary Search Tree	未評価
1305. All Elements in Two Binary Search Trees	1260
99. Recover Binary Search Tree	未評価
897. Increasing Order Search Tree	1473
2476. Closest Nodes Queries in a Binary Search Tree	1597
653. Two Sum IV Input Is a Bst	未評価
1373. Maximum Sum Bst in Binary Tree	1914
1932. Merge Bsts to Create Single Bst	2484

§2.10 Binary Treeの構築

問題	レーティング
108. Convert Sorted Array to Binary Search Tree	未評価
998. Maximum Binary Tree II	1498
1008. Construct Binary Search Tree From Preorder Traversal	1563
1382. Balance a Binary Search Tree	1541
2196. Create Binary Tree From Descriptions	1644
105. Construct Binary Tree From Preorder AND Inorder Traversal	未評価
106. Construct Binary Tree From Inorder AND Postorder Traversal	未評価
889. Construct Binary Tree From Preorder AND Postorder Traversal	1732
1028. Recover a Tree From Preorder Traversal	1797

§2.11 ノードの挿入 / 削除

問題	レーティング
701. Insert Into a Binary Search Tree	未評価
450. Delete Node in a Bst	未評価
669. Trim a Binary Search Tree	未評価

§2.12 Tree DP

問題	レーティング
337. House Robber III	未評価
968. Binary Tree Cameras	2124

§2.13 Binary Treeの BFS

問題	レーティング
102. Binary Tree Level Order Traversal	未評価
103. Binary Tree Zigzag Level Order Traversal	未評価
107. Binary Tree Level Order Traversal II	未評価
199. Binary Tree Right Side View	未評価
513. Find Bottom Left Tree Value	未評価
515. Find Largest Value in Each Tree Row	未評価
637. Average of Levels in Binary Tree	未評価
1161. Maximum Level Sum of a Binary Tree	1250
993. Cousins in Binary Tree	1288
2583. Kth Largest Sum in a Binary Tree	1374
1302. Deepest Leaves Sum	1388
2415. Reverse Odd Levels of Binary Tree	1431
1609. Even Odd Tree	1438
623. Add One Row to Tree	未評価
2471. Minimum Number of Operations to Sort a Binary Tree by Level	1635
2641. Cousins in Binary Tree II	1677
919. Complete Binary Tree Inserter	1691
958. Check Completeness of a Binary Tree	1703
863. All Nodes Distance K in Binary Tree	1663
662. Maximum Width of Binary Tree	未評価

§2.14 Linked List + Binary Tree

問題	レーティング
114. Flatten Binary Tree to Linked List	未評価
1367. Linked List in Binary Tree	1650
109. Convert Sorted List to Binary Search Tree	未評価
116. Populating Next Right Pointers in Each Node	未評価
117. Populating Next Right Pointers in Each Node II	未評価

§2.15 N 分木

問題	レーティング
589. N Ary Tree Preorder Traversal	未評価
590. N Ary Tree Postorder Traversal	未評価
559. Maximum Depth of N Ary Tree	未評価
429. N Ary Tree Level Order Traversal	未評価
427. Construct Quad Tree	未評価
558. Logical OR of Two Binary Grids Represented As Quad Trees	未評価

§2.16 その他

問題	レーティング
1261. Find Elements in a Contaminated Binary Tree	1440
1104. Path in Zigzag Labelled Binary Tree	1545
987. Vertical Order Traversal of a Binary Tree	1676
655. Print Binary Tree	未評価
979. Distribute Coins in Binary Tree	1709
222. Count Complete Tree Nodes	未評価
297. Serialize AND Deserialize Binary Tree	未評価
449. Serialize AND Deserialize Bst	未評価
331. Verify Preorder Serialization of a Binary Tree	未評価
652. Find Duplicate Subtrees	未評価
173. Binary Search Tree Iterator	未評価
2049. Count Nodes with the Highest Score	1912
2673. Make Costs of Paths Equal in a Binary Tree	1917
2509. Cycle Length Queries in a Tree	1948
2458. Height of Binary Tree After Subtree Removal Queries	2299

三、一般の木

§3.1 走査

問題	レーティング
2368. Reachable Nodes with Restrictions	1477
1466. Reorder Routes to Make All Paths Lead to the City Zero	1634

§3.2 トップダウン DFS

問題	レーティング
1376. Time Needed to Inform All Employees	1561
3528. Unit Conversion I	1580
1443. Minimum Time to Collect All Apples in a Tree	1683
1377. Frog Position After T Seconds	1824
3067. Count Pairs of Connectable Servers in a Weighted Tree Network	1909
3372. Maximize the Number of Target Nodes After Connecting Trees I	1927
2467. Most Profitable Path in a Tree	2053
3373. Maximize the Number of Target Nodes After Connecting Trees II	2162
1766. Tree of Coprimes	2232
2791. Count Paths That Can Form a Palindrome in a Tree	2677

§3.3 ボトムアップ DFS

問題	レーティング
690. Employee Importance	未評価
3249. Count the Number of Good Nodes	1566
1519. Number of Nodes in the Sub Tree with the Same Label	1809
3558. Number of Ways to Assign Edge Weights I	1845
3593. Minimum Increments to Equalize Leaf Paths	1959
2872. Maximum Number of K Divisible Components	1968
2477. Minimum Fuel Cost to Report to the Capital	2012
2973. Find Number of Coins to Place in Tree Nodes	2277
2440. Create Components with Same Value	2460

§3.4 行きと帰りの両方で処理する

問題	レーティング
3593. Minimum Increments to Equalize Leaf Paths	1959
3331. Find Subtree Sizes After Changes	2046

§3.5 木の直径

問題	レーティング
2246. Longest Path with Different Adjacent Characters	2126
3203. Find Minimum Diameter After Merging Two Trees	2266
1617. Count Subtrees with Max Distance Between Cities	2309
2538. Difference Between Maximum AND Minimum Price Sum	2398

§3.6 木のTopological Sort

問題	レーティング
310. Minimum Height Trees	未評価
2603. Collect Coins in a Tree	2712

§3.7 DFS のタイムスタンプ（オイラーツアー）

問題	レーティング
3515. Shortest Path in a Weighted Tree	2312
2322. Minimum Score After Removals on a Tree	2392
3327. Check If DFS Strings Are Palindromes	2454
3590. Kth Smallest Path XOR Sum	2646

§3.8 Lowest Common Ancestor (LCA)、ダブリング

問題	レーティング
1483. Kth Ancestor of a Tree Node	2115
3559. Number of Ways to Assign Edge Weights II	2146
3553. Minimum Weighted Subgraph with the Required Paths II	2411
3585. Find Weighted Median Node in Tree	2429
2846. Minimum Edge Weight Equilibrium Queries in a Tree	2508
2646. Minimize the Total Price of the Trips	2238

§3.9 木上のSliding Window

問題	レーティング
3425. Longest Special Path	2435
3486. Longest Special Path II	2925

§3.10 マージテク（sack）

問題	レーティング
2003. Smallest Missing Genetic Value in Each Subtree	2415
3590. Kth Smallest Path XOR Sum	2646
3575. Maximum Good Subtree Score	2360

§3.11 重心分解

問題	レーティング
3372. Maximize the Number of Target Nodes After Connecting Trees I	1927

§3.12 その他

問題	レーティング
2867. Count Valid Paths in a Tree	2428
2421. Number of Good Paths	2445
1719. Number of Ways to Reconstruct a Tree	3018

四、Backtracking

§4.1 入門Backtracking

問題	レーティング
17. Letter Combinations of a Phone Number	未評価

§4.2 部分集合型Backtracking

問題	レーティング
78. Subsets	未評価
1863. Sum of All Subset XOR Totals	1372
784. Letter Case Permutation	1342
3566. Partition Array Into Two Equal Product Subsets	1459
2044. Count Number of Maximum Bitwise OR Subsets	1568
2397. Maximum Rows Covered by Columns	1719
1239. Maximum Length of a Concatenated String with Unique Characters	1720
2212. Maximum Points in an Archery Competition	1869
1255. Maximum Score Words Formed by Letters	1882
2151. Maximum Good People Based on Statements	1980
2597. The Number of Beautiful Subsets	2023
2959. Number of Possible Sets of Closing Branches	2077
1601. Maximum Number of Achievable Transfer Requests	2119
1617. Count Subtrees with Max Distance Between Cities	2309

§4.3 分割型Backtracking

問題	レーティング
131. Palindrome Partitioning	未評価
2698. Find the Punishment Number of an Integer	1679
1593. Split a String Into the Max Number of Unique Substrings	1740
1849. Splitting a String Into Descending Consecutive Values	1747
93. Restore Ip Addresses	未評価
140. Word Break II	未評価

§4.4 組合せ型Backtracking

問題	レーティング
77. Combinations	未評価
216. Combination Sum III	未評価
1286. Iterator for Combination	1591
22. Generate Parentheses	未評価
301. Remove Invalid Parentheses	未評価

§4.5 順列型Backtracking

問題	レーティング
46. Permutations	未評価
3376. Minimum Time to Break Locks I	1793
51. N Queens	未評価
52. N Queens II	未評価
2850. Minimum Moves to Spread Stones Over Grid	2001
1718. Construct the Lexicographically Largest Valid Sequence	2080
1307. Verbal Arithmetic Puzzle	2250
37. Sudoku Solver	未評価

§4.6 重複要素のあるBacktracking

問題	レーティング
90. Subsets II	未評価
40. Combination Sum II	未評価
491. Non Decreasing Subsequences	未評価
47. Permutations II	未評価
1079. Letter Tile Possibilities	1741
3646. Next Special Palindrome Number	2445
2014. Longest Subsequence Repeated K Times	2558

§4.7 探索

問題	レーティング
3211. Generate Binary Strings Without Adjacent Zeros	1353
967. Numbers with Same Consecutive Differences	1433
2094. Finding 3 Digit Even Numbers	1455
1415. The K Th Lexicographical String of All Happy Strings of Length N	1576
1219. Path with Maximum Gold	1663
79. Word Search	未評価
980. Unique Paths III	1830
2002. Maximum Product of the Length of Two Palindromic Subsequences	1869
1255. Maximum Score Words Formed by Letters	1882
3669. Balanced K Factor Decomposition	1917
473. Matchsticks to Square	未評価
212. Word Search II	未評価
638. Shopping Offers	未評価
126. Word Ladder II	未評価
691. Stickers to Spell Word	未評価
2056. Number of Valid Move Combinations on Chessboard	2611
2386. Find the K Sum of an Array	2648
3509. Maximum Product of Subsequences with an Alternating Sum Equal to K	2703
488. Zuma Game	未評価

§4.8 半分全列挙

問題	レーティング
805. Split Array with Same Average	1983
494. Target Sum	未評価
3566. Partition Array Into Two Equal Product Subsets	1459
1755. Closest Subsequence Sum	2364
956. Tallest Billboard	2381
2035. Partition Array Into Two Arrays to Minimize Sum Difference	2490
3267. Count Almost Equal Pairs II	2545

五、その他のRecursion / Divide and Conquer

問題	レーティング
3537. Fill a Special Grid	1542
912. Sort an Array	未評価
880. Decoded String at Index	2011
3307. Find the K Th Character in String Game II	2232
1545. Find Kth Bit in Nth Binary String	1479
3614. Process String with Special Operations II	2011
932. Beautiful Array	2294

トラック 2 の最初の問題集です。ルートでは「文字列とオートマトン」の次がおすすめですが、学習契約を結ぶときにここを選べば、この問題集から始められます。

レーティングは zerotrac さんによる LeetCode コンテストレーティングです。zerotrac のレーティングがない問題は「未評価」と表示されます。

書斎を開く