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://play.golang.org/p/ZypZjFhhcnJ


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

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

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

ソース
https://play.golang.org/p/j20jPmrUGqF

実行結果

1
2
3
4
5
6
7
8
9
10

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

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

ソース
https://play.golang.org/p/5y1ykckcE1J

実行結果

1
2
3
4
5
6
7
8
9
10

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

ソース
https://play.golang.org/p/ZypZjFhhcnJ

実行結果

true
true
true
false
false
false
false
false
false

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