A Tour of Goの練習問題を解説するシリーズ(10/11) – Exercise: Equivalent Binary Trees

みなさん、こんにちは。人類をGopherにしたいと考えているまるりんです。

A Tour of Goはプログラミング言語Goの入門サイトです。 このシリーズではA Tour of Goの練習問題を解説します。

今回は以下の問題を扱います。

問題
Exercise: Equivalent Binary Trees
解答
https://go.dev/play/p/lT4l6FwHVq3

---

一見難しそうに見える問題ですが、着目点は以下です。

1. 木構造をどのようにたどるのか
2. どの処理でチャネルを使うのか

まず、木構造をどのようにたどるのか、ですが、問題文に例示されているツリーを左から深さ優先探索でたどった場合、昇順でソートされたフィボナッチ数列になりそうです。 ディレクトリをトラバースするイメージで木をたどります。goroutineはjoinできないので、wg.Add(1)してメインスレッドでgoroutineが終了するのを待ちます。 そうでない場合メインスレッドが先に終了して、結果に何も表示されなくなります。

ソース
https://go.dev/play/p/dfnNAC4_Xsm

実行結果

1
2
3
4
5
6
7
8
9
10

無事に値を表示できています。最初の値が1になっているのは左端からたどった場合の最深部+1ノード(tがnil)に到達してからreturnし(if t == nilが真)、戻った先のノードのt.Valueを表示しているからです。 表示後、右側のノードを見にいきます。 このあたりがイメージしづらい場合は、紙に図を書いてどのノードに進んで、どのノードに戻るのかを確認すると良いと思います。

次に、どの処理でチャネルを使うのか、ですがノードが持っているValueをチャネルに送信します。Walk()が終わってからチャネルをクローズしたいため、関数を分けました。 main()ではチャネルの値を受信します。

ソース
https://go.dev/play/p/kN20VmEg9bb

実行結果

1
2
3
4
5
6
7
8
9
10

ここまでくればSame()の処理は自明です。要は2つのチャネルから取り出した値を順に比較すれば良いのです。

ソース
https://go.dev/play/p/lT4l6FwHVq3

実行結果

true
true
true
false
false
false
false
false
false

この処理はチャネルを経由して2つのツリーの値を先頭から順に比較していき、ひとつでも違う値が見つかった時点で処理を終えられて効率的です。 マルチスレッドの恩恵を十分に享受しています。