LeetCode 練習問題集
問題 | 難易度 | 重要度 | テクニック |
★★★★ | 高 | 木の直径 | |
★★★★ | 高 | 強連結成分 | |
★★★★ | 中 | 関節点 & 橋 |
応用編では基礎編のダイクストラやトポロジカルソートと同程度の難易度の内容を扱います。グラフ自体が難しい分野であるため、より一層基礎編をしっかりと復習してから応用編にのぞみましょう。基礎編だけでも6, 7割の面接に対応できるくらいの力はつきます。
また本章では、グラフの中でも有名だが解き方を知らないと難しい問題を紹介します。ある意味知識問題として位置付けられますが、ただ解き方を暗記するのではなく、なぜそうなるかを理解して応用できるようにしましょう。
Tree Diameter（木の直径）
木の直径とは、その木の中で最も長い経路（パス）を指します。（最も遠い2つのノード間の距離です。）既に二分木（基礎）BFS, DFS - 例題2. Diameter（直径）で（重み無し）二分木での木の直径の求め方を一度解いています。今回は一般的な木での直径を求めます。
例題. Tree Diameter（木の直径）
難易度: ★★★ 重要度: 中
