LeetCode 練習問題集
問題 | 難易度 | 重要度 | テクニック |
★★ | 高 | Breadth First Search, BFS（幅優先探索） | |
★★★ | 高 | Breadth First Search, BFS（幅優先探索） | |
★★★ | 中 | Breadth First Search, BFS（幅優先探索） | |
★★★ | 高 | Depth First Search, DFS（深さ優先探索） | |
★★★ | 高 | Depth First Search, DFS（深さ優先探索） | |
★★ | 高 | Depth First Search, DFS（深さ優先探索） | |
★★ | 高 | Depth First Search, DFS（深さ優先探索） | |
★★ | 高 | Depth First Search, DFS（深さ優先探索） | |
★★ | 高 | Depth First Search, DFS（深さ優先探索） | |
★★ | 高 | Depth First Search, DFS（深さ優先探索） | |
★★★ | 高 | Depth First Search, DFS（深さ優先探索） | |
★★★★ | 高 | Depth First Search, DFS（深さ優先探索） |
事前に必要な知識
- 配列、キュー、スタック
- 再帰関数
本章ではBreadth First Search, BFS（幅優先探索）、 Depth First Search, DFS（深さ優先探索）の2つの探索について説明します。先に探索(Search)とは何をすることかついて説明します。簡単にいうとグラフ上のノードとエッジを通りながらグラフの構造を把握していくことです。二分木の問題では一般的にノードのクラス（構造体）は以下のコードのように事前に定義されています。そして問題では基本的に根のノードしか与えられません。 （
...はEllipsisと呼ばれる省略を表すPythonの組み込み定数です。公式ドキュメントから参照できます。）# ノードのクラス（構造体） class Node: def __init__(self, val, left=None, right=None): # ノードの値 self.val = val # 左の子ノード self.left = left # 右の子ノード self.right = right # 基本的には根しか与えられない def question(root: Node): ...