🏃

LeetCodeを解いて身に付ける木の巡回法

2021/01/17に公開

データ構造

概要

木構造が・・・

苦手だああああ！！！！

という方、意外と多いのではないかと思います。~~僕もそちら側です。~~

この記事では木の巡回方法とそれぞれの巡回方法に対応したLeetCodeの問題を取り上げます。
実際に理論を理解した後に問題を解いて理解を深めようという狙いです。

それでは始めましょう。

木の巡回とは？

木の巡回とは、木の全ての節点を特定のアルゴリズムを用いて訪れることです。
英語で言うならばtraverseです。
もしご自身で英語の記事や問題を探すときはTreeとTraverseもしくはTraversalで検索すればひっかかるかと思います。

多くの問題では各頂点が一回だけ現れるような木Tの頂点のリストを返り値として返すようなアルゴリズムの設計を求められます。

例えば、以下の問題は与えられた二分木を通りがけ順のリストで返すようなアルゴリズムを実装してください、という内容です。

例

root = [1,null,2,3]
Output: [1,3,2]

94. Binary Tree Inorder Traversal

アルゴリズムとデータ構造の問題の中では大きなカテゴリーの一つとなっており、例えばコーディング面接などでも頻出です。

巡回方法

原則として、根から出発し、全ての頂点を訪れるという方法がメインです。

木の巡回方法は大きく分けて二つの手法があります。

DFS

まず一つ目です。DFSとは、Depth First Searchの略です。日本語では深さ優先探索といいます。
現在地から出来るだけ木の深い方へと向かっていきます。

なお、深さ優先探索で探索した時にその要素を出力しようとすると以下の三つの方法が存在します。

行きがけ順
通りがけ順
帰りがけ順

DFS(行きがけ順)

英語ではpreorderと呼ばれる巡回方法です。

各頂点に到達した順に出力する形式のことです。
以下のような木の場合、巡回する順番は以下のようになります。

DFS(通りがけ順)

英語ではinorderと呼ばれる巡回方法です。

各頂点を左から右へと訪問する際に頂点番号を出力するという形式です。
以下のような木の場合、巡回する順番は以下のようになります。

DFS(帰りがけ順)

英語ではpostorderと呼ばれる巡回方法です。
各頂点を下から上に向かって巡回し、最後に訪問する際にその番号を出力します。

図解するならば以下の通りです。

BFS

二つ目です。Breadth First Searchの略です。日本語では幅優先探索と言います。
これは深さが同じ要素を順番に巡回し、それらの探索が住んだらもう一つ深い部分の要素へと探索対象を移して巡回を進めます。

こちらも図解しておきます、以下のイメージを持っておくと理解しやすいかもしれません。

大きく分けて二つあるのは分かったけど何が違うのさ？

そうですよね。その気持ち分かります。どっちでも要素は取れるんでしょ？なら好みの問題じゃない？と思ってしまうのも無理はありません。

実はこの二つの探索方法には深さ優先探索の方が得意なもの、幅優先探索の方が得意なものが存在し、それらを上手く使い分けることが大事なのです。

それぞれの使い分けとしてはざっくりとしたものになりますが、基本的に以下の認識で大丈夫です。

DFS
再帰関数を使うことで短く、簡潔に書ける
BFS
最短経路を求めたい時に使う。

LeetCodeでそれぞれの問題を解いてみよう！

LeetCodeで解いてみるとより理解が深まるかと思いましたので、それぞれの実装を試せるように各巡回方法の問題のリンクを貼っておきます。（会員登録必須）
難易度はEasyかMediumをメインに選んだので、きちんと理解できていれば解けるかと思います。
BFSだけHardの問題があります。自信がある方は是非解いてみて下さい。

もし解法を思いつかない場合はSolution(課金しなければならない場合もある)かDiscussを覗いて考え方を学ぶといいかと思います。