【ITニュース解説】🗓 Daily LeetCode Progress – Day 22

システム開発の世界では、問題を効率的に解決するためのアルゴリズムとデータ構造の知識が不可欠である。特に「木構造」と呼ばれるデータ構造は、ファイルシステムやデータベースの索引など、様々な場面で応用されており、その理解はエンジニアにとって重要な基礎となる。今回は、プログラミング問題解決プラットフォームであるLeetCodeで取り上げられた2つの問題を通じて、木構造の一種である「二分木」に関する基本的なアルゴリズムを解説する。

まず、最初の問題は「二分探索木（BST: Binary Search Tree）において、k番目に小さい要素を見つける」というものである。これを理解するためには、二分木と二分探索木の違いを知る必要がある。二分木は、各データ要素（ノード）が最大で2つの子ノードを持つ木構造だ。一方、二分探索木は二分木に「あるノードの左側の子孫はすべてそのノードより小さい値を持ち、右側の子孫はすべて大きい値を持つ」というルールを追加したものである。このルールにより、データの探索を非常に効率的に行うことが可能になる。

この問題の解決策として紹介されているのが「中間順巡回（Inorder Traversal）」という探索アルゴリズムだ。これは「左の子ノード → 自分自身（親ノード） → 右の子ノード」の順で木をたどっていく方法である。二分探索木の特性上、この順序でノードを訪れると、その値は自然と小さいものから大きいものへと並ぶことになる。つまり、二分探索木を中間順巡回すると、ソート済みのデータ列が得られるのだ。この性質を利用すれば、問題は簡単に解決できる。探索を開始し、ノードを訪れるたびにカウンターを1つずつ増やしていく。カウンターの値が指定された「k」と一致した瞬間、そのノードがk番目に小さい要素となる。この時点で探索を終了すれば、無駄な処理を省き、効率的に答えを導き出すことができる。

次に、2つ目の問題は「二分木における最小共通祖先（LCA: Lowest Common Ancestor）を見つける」というものだ。これは、木構造の中にある2つの指定されたノード（pとq）に共通する祖先ノードのうち、最も深い位置にあるもの（つまり、2つのノードに最も近い共通の親）を探し出す問題である。こちらは二分探索木ではない、より一般的な二分木が対象となる。

この問題に対しては、「分割統治法（Divide and Conquer）」を用いた再帰的なアプローチが非常に有効だ。分割統治法とは、大きな問題を小さな部分問題に分割し、それぞれの部分問題を解決した結果を組み合わせて、最終的に元の問題の答えを得る手法である。具体的には、木の根から探索を開始する関数を定義し、その関数が自分自身を呼び出す「再帰」を利用して木を深くたどっていく。探索の過程で、もし現在のノードが探しているpかqのどちらかと一致した場合、そのノードを結果として返す。一致しない場合は、現在のノードの左の部分木と右の部分木に対して、同じ探索処理を再帰的に実行する。そして、その左右の探索結果を調べる。もし、左の部分木からpが見つかり、右の部分木からqが見つかった場合（あるいはその逆）、現在のノードがpとqを左右に分ける分岐点、すなわち最小共通祖先であると断定できる。もし片方の部分木からしかpまたはqが見つからなかった場合は、その見つかったノードをそのまま上層の呼び出し元に返していく。この処理を繰り返すことで、最終的に最小共通祖先が特定される。

今回取り上げた2つの問題は、それぞれ二分探索木の特性を活用した探索と、一般的な二分木に対する再帰的な分割統治法という、アルゴリズムの基本的ながらも強力なパターンを示している。こうした典型的な問題の解法を学ぶことは、単にコーディングスキルを向上させるだけでなく、複雑な問題を小さな要素に分解して考える論理的思考力を養う上で極めて重要である。日々の学習を通じてこれらのパターンに習熟することが、優れたシステムエンジニアへの確かな一歩となるだろう。