はじめに
Go を学習し始めの時はあまり納得のいく回答ができなかったが、少し Go にも慣れてきて再度挑戦してある程度納得のいく回答ができたので書き留めます。
※ 実装には基本的な型のみを利用し、contextといったものの利用は避けています
問題の意図
問題文から読み取れる意図をまとめます。
問題文（もしくは Tree のドキュメント）には
関数 tree.New(k) は、値( k, 2k, 3k, ..., 10k )をもつ、ランダムに構造化 (しかし常にソートされています) した二分木を生成します。
と書かれているので生成される必ず10個のノードを持つ二分探索木となります。
実際、tree パッケージの tree.New() の実装を確認すると確かに10個の値を持つ二分探索木を作成していることがわかります。
つまり、この問題では
- 生成される二分木は二分探索木である
- その二分探索木は必ず10個のノードを持つ
ということを前提として処理を実装してみてくださいという意図があるのかなと思います。
func New(k int) *Tree {
var t *Tree
for _, v := range rand.Perm(10) {
t = insert(t, (1+v)*k)
}
return t
}
func insert(t *Tree, v int) *Tree {
if t == nil {
return &Tree{nil, v, nil}
}
if v < t.Value {
t.Left = insert(t.Left, v)
} else {
t.Right = insert(t.Right, v)
}
return t
}
回答１
こちらの回答は問題の意図をくみ取り、生成される二分木が必ず10個のノードを持つという前提のもと実装した処理です。
比較する二つの二分木が必ず10個のノードを持つことを前提として処理を実装しているため、Same()関数内ではWalk()の終了タイミングを知ることなく処理を書くことができています。
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// 二分木を全探査して、小さい値のものからチャネルで送信する
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
if t.Left != nil {
Walk(t.Left, ch)
}
ch <- t.Value
if t.Right != nil {
Walk(t.Right, ch)
}
return
}
// 比較する二分木がすべて同じ値を持つか判定
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for i := 0; i < 10; i++ {
v1, v2 := <-ch1, <-ch2
if v1 != v2 {
return false
}
}
return true
}
func main() {
fmt.Println(Same(tree.New(1), tree.New(1)))
}
回答２
二分木に含まれるノードの数が10個であるという前提で処理を実装するのは少し釈然としてないので、比較する二分木として
- 二分木は二分探索木である
のみを条件とした処理も実装してみました。
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
if t.Left != nil {
Walk(t.Left, ch)
}
ch <- t.Value
if t.Right != nil {
Walk(t.Right, ch)
}
return
}
func Same(t1, t2 *tree.Tree) bool {
walk := func(t *tree.Tree) <-chan int {
ch := make(chan int)
go func() {
Walk(t, ch)
close(ch)
}()
return ch
}
ch1 := walk(t1)
ch2 := walk(t2)
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
// 片方だけノードの値を受け取れなかった（木のサイズが違う） or
// ノードの値が異なる
if xor(ok1, ok2) || v1 != v2 {
return false
}
// 比較するノードがなくなった
if !ok1 && !ok2 {
return true
}
}
}
func xor(b1, b2 bool) bool {
return (b1 || b2) && !(b1 && b2)
}
func main() {
fmt.Println(Same(tree.New(1), tree.New(2)))
}
回答１との差異を簡単に保続していきます。
木に含まれるノードの数が不特定となったため、二分木の探査が終了したことを通知する必要があります。
ただ、Walk()関数は再帰的に処理しているためその中で close(ch) を利用してチャネルを閉じて通知することは難しいので、Same()関数内で以下の無名関数を定義しています。
※実際には今の
Walk()をwalk()に変更して外部から呼び出せないようにして、
ここで定義したwalk()をWalk()として外部からでも呼び出せるようにするほうが個人的には好き。
もっと言えば、walk()にcontext.Contextを渡して呼び出し先も呼び出し元が終了したことを認識できるにしたほうが良い気もするがここではそこまで考えない）
walk := func(t *tree.Tree) <-chan int {
ch := make(chan int)
go func() {
Walk(t, ch)
close(ch)
}()
return ch
}
次にノードの比較部分ですが、木のサイズが等しいという条件がないのでチャネルの状態を確認することで木のサイズが異なっているかどうか判定しています。
片方のみのチャネルが閉じている場合は木のサイズが異なると判断し、
両方のチャネルが同じ状態である場合はまだノードがあるので処理を続ける、もしくは比較ノードがなくなったのですべて同じノードを持つとして処理を終了します。
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
// 片方だけノードの値を受け取れなかった（木のサイズが違う） or
// ノードの値が異なる
if xor(ok1, ok2) || v1 != v2 {
return false
}
// 比較するノードがなくなった
if !ok1 && !ok2 {
return true
}
}